View Code
1 //hdu2087
2 #include <iostream>
3 #include <string>
4 #include <cstring>
5 using namespace std;
6 string str1,str2;
7 int next[1005];
8 void get()
9 {
10 int i = 0;
11 int j = -1;
12 memset(next,0,sizeof(next));
13 next[0] = -1;//不加的话会死循环,因为 j = next[j]（j=0） 会赋一个垃圾数字
14 while(i<str2.length())
15 {
16 if(j==-1||str2[i]==str2[j])
17 {
18 i++;
19 j++;
20 next[i] = j;
21 }
22 else
23 j = next[j];
24 }
25 }
26 int kmp()
27 {
28 int i = 0, j = 0;
29 int cnt = 0;
30 while(i<str1.length())
31 {
32 if(j==-1||str1[i]==str2[j])
33 {
34 i++;
35 j++;
36 if(j==str2.length())
37 {
38 cnt++;
39 j=0;
40 }
41 }
42 else
43 j = next[j];
44 }
45 return cnt;
46 }
47 int main()
48 {
49 while(cin>>str1)
50 {
51 if(str1[0]=='#')
52 break;
53 cin>>str2;
54 get();
55 int cnt = kmp();
56 cout<<cnt<<endl;
57 str1.clear();
58 str2.clear();
59 }
60 return 0;
61 }
1 //模式串在主串中出现次数
2 //估计find会超时
3 //不论哪一个next函数均可ＡＣ
4 #include <iostream>
5 #include <cstring>
6 #include <string>
7 using namespace std;
8 string s1,s2;
9 int next[10005];
10 void get()
11 {
12 int i = 0;
13 int j = -1;
14 memset(next,0,sizeof(next));
15 next[0] = -1;//不加的话会死循环,因为 j = next[j]（j=0） 会赋一个垃圾数字
16 while(i<s1.length())
17 {
18 if(j==-1||s1[i]==s1[j])
19 {
20 i++;
21 j++;
22 // if(s1[i]!=s1[j])
23 next[i] = j;
24 // else
25 // next[i] = next[j];
26 }
27 else
28 j = next[j];
29 }
30 }
31 int kmp()
32 {
33 int i = 0, j = 0;
34 int cnt = 0;
35 while(i<s2.length())//(i<=(s2.length()-s1.length()))不行
36 {
37 if(j==-1||s1[j]==s2[i])
38 {
39 i++;
40 j++;
41 }
42 else
43 j = next[j];
44 if(j==s1.length())
45 {
46 cnt++;
47 j = next[j];//此处改为j = 0就变成减花布条那一题啦
48 }
49 }
50 return cnt;
51 }
52 int main()
53 {
54 int i,j,k,T;
55 cin>>T;
56 while(T--)
57 {
58 s1.clear();
59 s2.clear();
60 cin>>s1;
61 cin>>s2;
62 get();
63 int cnt = kmp();
64 cout<<cnt<<endl;
65 }
66 return 0;
67 }
68
69
View Code
//超时，即便全为C风格也超时
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
string s1,s2;
int next[10005];
void get()
{
int i = 0;
int j = -1;
memset(next,0,sizeof(next));
next[0] = -1;//不加的话会死循环,因为 j = next[j]（j=0） 会赋一个垃圾数字
while(i<s1.length())
{
if(j==-1||s1[i]==s1[j])
{
i++;
j++;
if(s1[i]!=s1[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[j];
}
}
int kmp()
{
int i = 0, j = 0;
int cnt = 0;
while(i<s2.length())//(i<=(s2.length()-s1.length()))不行
{
if(j==-1||s1[j]==s2[i])
{
i++;
j++;
if(j==s1.length())
{
cnt++;
i = i-j+1;
j = 0;
}
}
else
j = next[j];
}
return cnt;
}
int main()
{
int i,j,k,T;
cin>>T;
while(T--)
{
s1.clear();
s2.clear();
cin>>s1;
cin>>s2;
get();
int cnt = kmp();
cout<<cnt<<endl;
}
return 0;
}
