傳送門：
Oulipo
題意：
很裸的字串匹配題
給大小兩字串，在大字串中找小字串的出現次數，可重疊。
思路：
主要練習各種解法，順便驗證模板，包含：
KMP模板 HASH模板 Z algorithm模板
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// kmp
int T,M,N,K,I,a,b,c,ans,cnt;
string s,p;
int nxt[10005];
void build(string &s){
memset(nxt, 0, sizeof(nxt));
for(int i=2;i<=s.length();i++){
int p = nxt[i-1];
while(p>0 && s[i-1] != s[p])
p = nxt[p];
if(s[i-1] == s[p])
p++;
nxt[i] = p;
}
}
int kmp(string &s, string &p){
if(p.length() > s.length())
return 0;
int ans = 0, cnt=0;
build(p);
for(int i=0;i<s.length();i++){
while(cnt>0 && s[i] != p[cnt])
cnt = nxt[cnt];
if(s[i] == p[cnt])
cnt++;
if(cnt == p.length()){
ans++;
cnt = nxt[cnt];
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>N;
while(N--){
cin>>p>>s;
cout<<kmp(s, p)<<endl;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// z algorithm
string s,p;
int N, z[1020000];
void z_value(string s){
int l=0, r=0;
for(int i=1;i<s.length();i++){
int j = max(min(z[i-l], r-i), 0);
for(; i+j<s.length() && s[i+j]==s[j];j++);
z[i] = j;
if(i+z[i] > r){
r = i+z[i];
l = i;
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>N;
while(N--){
cin>>p>>s;
z_value(p+"$"+s);
int len = p.length() + s.length() + 1, ans = 0;
for(int i=0;i<len;i++) if(z[i] == p.length())
ans ++;
cout<<ans<<endl;
}
}
1
// hash 故障了待補