亚洲欧美日韩国产综合在线,欧美日韩亚洲一区二区三区在线 ,国产日韩一区二区三区在线播放

P3080

枚舉+kmp..再不練kmp都忘了..orz
wa了一次..注意一下求出的串要最小的那個(gè)

#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 閱讀(99) 評(píng)論(0) 編輯收藏引用所屬分類: 數(shù)據(jù)結(jié)構(gòu)與算法

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

P3080