HDU 5782 Cycle —

HDU 5782 Cycle —— KMP

题目：Cycle

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5782

题意：给出两个字符串，判断两个字符串的每一个前缀是否循环相等（比如abc 和 cab相等），是输出一个1，否输出一个0，最后回车。

思路：

　　kmp

　　令s1为第一个字符串，s2为第二个字符串，先假设s1不可以循环，即s1的abc 不能变为cab，而s2可以。

　　s1不可以循环，我们可以算出s1的next数组，然后用kmp匹配两个字符串是否循环相等，假设现在正在匹配 s1=abba 和 s2=baab，i 指针指在s1，j 指针指在s2，如果s1[i]和s2[j]不等，i = next[j]，这些和普通的kmp一样（s2当做原串，s1当做模式串），不同的是等j 指向了s2的末尾，也就是说确认了s1的前缀ab 和 s2的后缀ab相等，那么j 变为0，再判断s2[j] 是否和 s1[i]相等，如果一直相等直到s1[i]=0，那么说明两个字符串循环相等，如果中间跳出，则可以判断两个字符串不循环相等。

　　如果按照上面的方法进行，n*n的时间判断完，有可能会超时，但我们可以发现一个缩短时间的地方。

　　比如：abbaa 和 baaba，我们在上一次计算已经算出s1的前缀ab 和上次s2的后缀ab 相等，其他前面的情况也判断过了，那么我们就不需要再重新判断这些了，i 指针可以直接从baa的b开始，j 指针可以直接从最后一个字符开始，同样判断到i 指针指向s1的结束符结束，这样可以缩短大量的时间，碰上aa...a 和 aa...a，就只要遍历一遍就ok了。

　　上面的判断过程基于s1不循环，如果碰上bbab 和 babb 就不行了，那么我们再定义s2不循环，s1可以循环，再判断一遍，最后将两个成果或运算即可（即满足一种就可以）。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int next[10010];
 4 char s[10010];
 5 char st[10010];
 6 void get_next(char *s)
 7 {
 8   next[0]=-1;
 9   next[1]=0;
10   int i=1,j=0;
11   while(s[i])
12   {
13     if(s[i]==s[j]) next[++i]=++j;
14     else if(next[j]!=-1) j=next[j];
15     else next[++i]=0;
16   }
17 }
18 
19 int kmp(int len,int &duan,char *s,char *st)
20 {
21   int ret=0;
22   int i=len,j=duan;
23   while(i<=len)
24   {
25     if(st[i]==s[j])
26     {
27       i++;
28       j++;
29     }
30     else if(next[j]!=-1) j=next[j];
31     else i++;
32   }
33   duan=j;
34   for(i=0;j<=len;i++,j++)
35   {
36     if(st[i]!=s[j]) break;
37   }
38   if(j>len) return 1;
39   return 0;
40 }
41 int ans[10010];
42 int main()
43 {
44   while(scanf("%s%s",s,st)!=EOF)
45   {
46     int duan=0;
47     get_next(s);
48     for(int i=0;s[i];i++)
49     {
50       ans[i]=kmp(i,duan,s,st);
51     }
52     duan=0;
53     get_next(st);
54     for(int i=0;s[i];i++)
55     {
56       ans[i]|=kmp(i,duan,st,s);
57     }
58     for(int i=0;s[i];i++)
59       printf("%d",ans[i]);
60     printf("
");
61   }
62   return 0;
63 }