hdu 2594 Simpsons’ Hidden Talents

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2594

题意前面一堆废话，就是问给出两个字符串s1和s2,问s1的前缀和s2的后缀最大匹配的数量，

这很容易让人想到KMP中求next数组的方法，所以这里可以把s1，s2连接起来，strcat(s1，s2)该函数的作用就是把s2连接到s1的末端

连接完之后就是对串s1进行求next代码详见kMP,接下来就是判断next[k]与len1和len2的关系

如果next[k]大于len1或len2,则继续回溯k=next[k];

这样判断next[k]是否为零，为零则没有匹配，不为零输出next[k]即是最大的匹配数

View Code

 1 # include <string.h>
 2 # include <stdio.h>
 3 int len, len1, len2;
 4 int next[50005*2];
 5 char s1[50005],s2[50005];
 6 void COUNT_next(char *s1)
 7 {
 8     int i=0,j=-1;
 9     next[0]=-1;
10     while(i<len)
11     {
12         if(j==-1 || s1[i]==s1[j])
13         {
14             ++i;
15             ++j;
16             next[i]=j;
17         }
18         else j = next[j];
19     }
20 }
21 int main()
22 {
23 
24     int i;
25     while(scanf("%s",s1) != EOF)
26     {
27         scanf("%s",s2);
28         len1=strlen(s1);
29         len2=strlen(s2);
30         len = len1+len2;
31         strcat(s1,s2);
32 
33         COUNT_next(s1);
34         int k=len;
35         while(next[k]>len1 || next[k]>len2)
36             k=next[k];
37         if(next[k]==0)
38             printf("0\n");
39         else
40         {
41             for(i=0;i<next[k];i++)
42                 printf("%c",s1[i]);
43             printf(" %d\n",next[k]);
44         }
45     }
46     return 0;