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到現在了:-( 。。。