http://acm.hdu.edu.cn/showproblem.php?pid=1867
这题输出有点麻烦 两个KMP 找出从一个字符串开头到令一个字符串结尾匹配的最大长度 再根据字符串比较函数字典序输出
View Code
1 #include<stdio.h> 2 #include<string.h> 3 char c1[100001],c2[200001],c3[100001],c4[200001]; 4 int next[100001]; 5 int kmp(char *a,char *b) 6 { 7 int k1 = strlen(a),k2 = strlen(b),i,j,y; 8 y = -1; 9 memset(next,0,sizeof(next)); 10 next[0] = -1; 11 for(i = 1 ; i < k2 ; i++) 12 { 13 while(y>-1&&b[y+1]!=b[i]) 14 y = next[y]; 15 if(b[y+1]== b[i]) 16 y++; 17 next[i] = y; 18 } 19 y=-1; 20 next[0] = -1; 21 for(i = 0 ;i < k1 ; i++) 22 { 23 while(y>-1&&a[i]!=b[y+1]) 24 y = next[y]; 25 if(a[i]==b[y+1]) 26 y++; 27 if(y == k2-1) 28 { 29 if(i == k1-1) 30 return y+1; 31 y = next[y]; 32 } 33 34 } 35 if(i==k1) 36 return y+1; 37 else 38 return 0; 39 } 40 int main() 41 { 42 int i,j,k,n,m,k1,k2; 43 while(scanf("%s %s", c1,c2)!=EOF) 44 { 45 int n1 = kmp(c1,c2); 46 int n2 = kmp(c2,c1); 47 k1 = strlen(c1); 48 k2 = strlen(c2); 49 if(n1==n2) 50 { 51 if(strcmp(c1,c2)<0) 52 { 53 printf("%s", c1); 54 for(i = n1 ; i < k2 ; i++) 55 printf("%c",c2[i]); 56 printf("\n"); 57 } 58 else 59 { 60 printf("%s", c2); 61 for(i = n1 ; i < k1 ; i++) 62 printf("%c",c1[i]); 63 printf("\n"); 64 } 65 } 66 else 67 if(n1>n2) 68 { 69 printf("%s", c1); 70 for(i = n1 ; i < k2 ; i++) 71 printf("%c",c2[i]); 72 printf("\n"); 73 } 74 else 75 { 76 printf("%s", c2); 77 for(i = n2 ; i < k1 ; i++) 78 printf("%c",c1[i]); 79 printf("\n"); 80 } 81 } 82 return 0; 83 }