POJ 3080 多个串最长公共子序列

求多个串最长公共子序列，字典序最小输出。枚举剪枝+kmp.比较简单，我用find直接查找16ms

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

string s[61];

int main()

{

    int ta;

    cin>>ta;

    int n;

    while(ta--)

    {

        cin>>n;

        string ans;

        for(int i=0;i<n;i++)

            cin>>s[i];

        int len=s[0].size();

        int max=2;

        for(int i=0;i<=len-max;i++)    //最优化剪枝

        {

            for(int j=len;j>=i+max;j--)

            {

               string ts(&s[0][i],&s[0][j]);  //对象的赋值

               int mark=1;

                for(int k=1;k<n;k++)

                {

                    if(s[k].find(ts)==4294967295)   //找不到

                    {

                      mark=0;

                      break;

                    }

                }

                if(mark&&ts.size()>=max)

                {

                    if(ts.size()>max)

                       {

                        max=ts.size();

                        ans=ts;

                       }

                       else

                            if(ts<ans)

                            {

                                ans=ts;

                            }

                }

            }

        }

        if(max==2)

        cout<<"no significant commonalities"<<endl;

        else cout<<ans<<endl;

    }

}

巴特西

POJ 3080 多个串最长公共子序列

最新文章

热门文章