首页 > 代码库 > HDU 2594 Simpsons’ Hidden Talents
HDU 2594 Simpsons’ Hidden Talents
经典扩展kmp。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 void getA (char *T,int *A){ 7 int j=0; 8 int len=strlen (T); 9 while(1+j<len&&T[0+j]==T[1+j])10 j = j + 1;11 A[1]=j;12 int k=1;13 for(int i=2; i<len; i++){14 int Len = k + A[k] - 1,L = A[i-k];15 if( L < Len - i + 1 )16 A[i] = L;17 else{18 j = max(0,Len -i +1);19 while(i+j<len&&T[i+j] == T[0+j])20 j = j + 1;21 A[i] = j,k = i;22 }23 }24 }25 26 void getB (char *S,char *T,int *A,int *B){27 getA (T,A);28 int j = 0;29 int lens=strlen (S);30 int lent=strlen (T);31 while(j<lens&&j<lent&&T[0+j]==S[0+j])32 j = j + 1;33 B[0] = j;34 int k = 0;35 for(int i=1; i<lens; i++) {36 int Len = k + B[k] - 1,L = A[i-k];37 if( L < Len - i + 1 )38 B[i] = L;39 else {40 j = max(0,Len -i +1);41 while(i+j<lens&&j<lent&&S[i+j] == T[0+j])42 j = j + 1;43 B[i] = j,k = i;44 }45 }46 }47 48 char S[200000],T[200000];49 int A[200000],B[200000];50 int main (){51 while (~scanf ("%s %s",S,T)){52 getB (T,S,A,B);53 int lent=strlen(T);54 int ans=0;55 for (int i=0;i<lent;i++){56 if (i+B[i]==lent){57 ans=B[i];58 break ;59 }60 //cout<<B[i]<<" ";61 }62 if (ans){63 for (int i=0;i<ans;i++)64 printf ("%c",S[i]);65 printf (" ");66 }67 cout<<ans<<endl;68 }69 return 0;70 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。