KMP，精妙，前后看了3次，到现在终于弄懂了，网上的各种模版很杂，错的也不少，自己写了个。。。
最妙的是next数组的运用，PKU上不少题是不用kmp()函数而巧妙运用next[]数组的。。。
getnext()实际也是一个自身的KMP匹配，怎一个妙字了得~ 广为流传的求法实在是精练，一字不改地照搬了~~
1
#include<stdio.h>
2
#include<string.h>
3
4
int next[255];
5
char m[255],s[255];
6
int cnt,res[255];
7
8
void getnext()
9
{
10
int i,j;
11
i=0;j=-1;
12
next[0]=-1;
13
while(s[i])
14
{
15
if(j==-1||s[i]==s[j])
16
next[++i]=++j;
17
else
18
j=next[j];
19
}
20
}
21
22
void kmp()
23
{
24
int i,j,len1,len2;
25
i=0;j=0;
26
len1=strlen(m);
27
len2=strlen(s);
28
while(i<len1)
29
{
30
while(j!=len2&&m[i]==s[j])//找到当前第一个失配字符
31
{
32
i++;
33
j++;
34
}
35
if(j==0)//第一个字符失配
36
i++;
37
else if(j==len2)//找到一个匹配串
38
{
39
res[cnt++]=i-j;
40
j=next[j];
41
}
42
else//回朔
43
j=next[j];
44
}
45
}
46
47
int main()
48
{
49
freopen("in.txt","r",stdin);
50
scanf("%s%s",m,s);
51
// m[]="aabbbabaabbaaabbaabbaabbaabbaabbaa",s[]="aabbaabb";
52
cnt=0;
53
getnext();
54
kmp();
55
return 0;
56
}
还有恶心的3450，WA到现在了:-( 。。。