InTheBloodHorse

每日一题(51) hud2087剪花布条

字数统计: 293阅读时长: 1 min
2019/01/16 Share

题目地址

题意

给一个主字符串和一个模式字符串,要求找到匹配的个数。例如 aaaaa aa 答案为2

思路

简单的kmp,当匹配成功的时候,要移动i的坐标,避免重复匹配

AC代码:

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
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
int nextval[1005];
int ans[1005];
int index;
void gen(string s){
nextval[0]=0;
nextval[1]=0;
int k=0;
for(int i=1;i<s.size();i++){
while(k>0 && s[k]!=s[i]) k = nextval[k];
if(s[k]==s[i]) k++;
nextval[i+1]=k;
}
nextval[0]=-1;
}

void kmp(string s, string p)
{
int lens=s.size(); //主字符串
int lenp=p.size(); //模式字符串
int i=0,j=0;
while(i<lens && j<lenp){
//因为在得到next数组的时候,最后把next[0] = -1
//所以j==-1代表当前无意义,重新匹配
if( j==-1 || s[i]==p[j]){
i++;
j++;
}else j=nextval[j];
if(j==lenp){
ans[index++]=i-j;
//回退
j=nextval[j];
i+=(p.size()-1);
}
}
}

int main()
{
string s,p;
// 主字符串s ,模式串p
while(cin >> s){
index=0;
memset(nextval,0,sizeof(nextval));
if(s=="#") break;
cin >> p;
gen(p);
kmp(s,p);
cout << index << endl;
}
}

CATALOG
  1. 1. 题意
  2. 2. 思路