kuangbin专题十六 KMP&&扩展KMP HDU1238 Substrings
发布时间:2020-12-14 05:14:22 所属栏目:大数据 来源:网络整理
导读:You are given a number of case-sensitive strings of alphabetic characters,find the largest string X,such that either X,or its inverse can be found as a substring of any of the given strings. InputThe first line of the input file contains a
You are given a number of case-sensitive strings of alphabetic characters,find the largest string X,such that either X,or its inverse can be found as a substring of any of the given strings.
InputThe first line of the input file contains a single integer t (1 <= t <= 10),the number of test cases,followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 100),the number of given strings,followed by n lines,each representing one string of minimum length 1 and maximum length 100. There is no extra white space before and after a string. OutputThere should be one line per test case containing the length of the largest string found. Sample Input 2 3 ABCD BCDFF BRCD 2 rose orchidSample Output 2 2 1 #include<stdio.h> 2 #include<iostream> 3 #include<string> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 int _,n,Next[110]; 8 vector<string> t; 9 10 void prekmp(string s) { 11 int len=s.size(); 12 int i,j; 13 j=Next[0]=-1; 14 i=0; 15 while(i<len) { 16 while(j!=-1&&s[i]!=s[j]) j=Next[j]; 17 Next[++i]=++j; 18 } 19 } 20 21 int kmp(string t,string p) { 22 int lent=t.size(),lenp=p.size(); 23 int i=0,j=0,ans=-1,res; 24 res=-1; 25 while(i<lent) { 26 while(j!=-1&&t[i]!=p[j]) j=Next[j]; 27 ++i;++j; 28 res=max(res,j); 29 } 30 ans=max(ans,res); 31 reverse(t.begin(),t.end()); 32 res=-1; 33 i=0,j=0; 34 while(i<lent) { 35 while(j!=-1&&t[i]!=p[j]) j=Next[j]; 36 ++i;++j; 37 res=max(res,j); 38 } 39 ans=max(ans,res); 40 return ans; 41 } 42 43 int main() { 44 // freopen("in","r",stdin); 45 for(scanf("%d",&_);_;_--) { 46 scanf("%d",&n); 47 string s; 48 for(int i=0;i<n;i++) { 49 cin>>s; 50 t.push_back(s); 51 } 52 string str=t[0],tempstr; 53 int len=str.size(),maxx=-1; 54 for(int i=0;i<len;i++) { 55 tempstr=str.substr(i,len-i); 56 int ans=0x3f3f3f; 57 prekmp(tempstr); 58 for(int j=1;j<t.size();j++) { 59 ans=min(kmp(t[j],tempstr),ans); 60 } 61 maxx=max(maxx,ans); 62 } 63 printf("%dn",maxx); 64 t.clear(); 65 } 66 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |