c++动态规划+暴力

暴力

using namespace std;
int res,cnt;
int maxstring(string ss,string s0){
    res=0,cnt=-1;
    int size=ss.size();
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            if(s0.find(ss.substr(i,j-i+1))!=s0.npos){
                if(res>=j-i+1)continue;
                else {
                    res=j-i+1;
                    //cout<<ss.substr(i,j-i+1)<<endl;
                    cnt=i;
                }
            }
        }
    }
    return cnt;
}
int main(){
    string s,s1;
    while(cin>>s>>s1){
        int size1=s.size(),size2=s1.size();
        if(size1<=size2)cout<<s.substr(maxstring(s, s1),res)<<endl;
        else cout<<s1.substr(maxstring(s1, s),res)<<endl;
    }
    return 0;
}

动态规划

using namespace std;
int res,indexx;
string index(string s1,string s2){
    res=0,indexx=-1;
    int size1=s1.size(),size2=s2.size();
    int f[size1+1][size2+1];
    memset(f,0,sizeof f);
    for(int i=0;i<=size1;i++)f[i][0]=0;
    for(int i=0;i<=size2;i++)f[0][i]=0;
    for(int i=1;i<=size1;i++){
        for(int j=1;j<=size2;j++){
            if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=0;
            if(res<f[i][j]){
                res=f[i][j];
                indexx=i-1;
            }
        }
    }
    return s1.substr(indexx-res+1,res);
}
int main(){
    string s,s1;
    while(cin>>s>>s1){
        int size1=s.size(),size2=s1.size();
        if(size1<=size2)cout<<index(s,s1)<<endl;
        else cout<<index(s1, s)<<endl;
    }
    return 0;
}