巢穴

about:blank

P3080

枚举+kmp..再不练kmp都忘了..orz
wa了一次..注意一下求出的串要最小的那个

#include <iostream>
#include <string>
//#include <fstream>
using namespace std;
//ifstream fin("t3080.in");
const int MAXN=100;
int k;
int n;
string str[MAXN];
string s_,result;
int p[MAXN];
void match_self()
{
     memset(p,sizeof(p),0);
     p[0]=-1;
     int x=-1;
     for (int i=1;i<s_.length();i++)
     {
         while (x>-1&&s_[x+1]!=s_[i]) x=p[x];
         if (s_[x+1]==s_[i]) x++;
         p[i]=x;
     }
}
bool match(string s)
{
     int x=-1;
     for (int i=0;i<s.length();i++)
     {
      while (x>-1&&s_[x+1]!=s[i]) x=p[x];
      if (s_[x+1]==s[i]) x++;
      if (x==s_.length()-1) return true;
      //p[i]=x;
     }
     return false;
}
int main()
{
    cin>>k;
    while(k--)
    {
     cin>>n;
     bool ok=false;
     for (int i=1;i<=n;i++)
     {
         cin>>str[i];
     }
     string st=str[1];
     for (int i=st.length();(i>=3)&&(ok==false);i--)
     {
      for (int j=0;(j<=i+j-1)&&(i+j-1<st.length());j++)
      {
       s_=st.substr(j,i);
       match_self();
       int count=0;
       for (int k=2;k<=n;k++)
       {
        if (match(str[k])) count++;
       }
       if (n-1==count)
       {
        if (!ok) result=s_; else if (result>s_) result=s_;
        ok=true;
       }
      }
     }
     if (ok)
     {
      cout<<result<<endl;
     }
     else
     {
      cout<<"no significant commonalities"<<endl;
     }
    }
    system("pause");
    return 0;
}

posted on 2009-10-19 21:30 Vincent 阅读(73) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理