最長公共子串

#include<iostream>
#include<string>
#include<vector>
using namespace std;

string LCS(string &str1, string &str2)
{
    string result;
    vector<int> num(str2.size(), 0);
    int maxLength = 0, last = 0;
    
    for(int i = 0; i < str1.size(); i++)
        for(int j = 0; j < str2.size(); j++)
        {
            if(str2[j] == str1[i])
            {
                if(i == 0 || j == 0) num[j] = 1;
                else num[j] = num[j-1] + 1;
                if(num[j] > maxLength)
                {
                    maxLength = num[j];
                    last = j;
                }
                
            }
        }
    cout << maxLength << endl << last;
    
    for(int i = last+1-maxLength; i <= last; i++)
        result += str2[i];
    
    
    
    return result;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    string str1,str2;
    cin >> str1 >> str2;
    if(str1.size() == 0 || str2.size() == 0) cout << "";
    
    
    cout << LCS(str1, str2);
    return 0;
}

參考文獻

經典算法題每日演練——第四題 最長公共子序列