KMP专题(不包含扩展KMP)

本文从WordPress迁移而来, 查看全部WordPress迁移文章

全部题目:

自家模板:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#define MAXS 1000010
#define MAXT 10010

class KMP{
//s串和t串下标均从0开始
public:
char s[MAXS],t[MAXT];
int lens,lent,next[MAXT];
int save[MAXS],ns;
void init(char *ss,char *tt){
ns = 0;
lens = strlen(ss);
lent = strlen(tt);
for(int i = 0; ss[i]; i++) s[i] = ss[i];
for(int i = 0; tt[i]; i++) t[i] = tt[i];
s[lens] = t[lent] = '\0';
}
void getNext(){
int i = 0 , j = -1;
next[0] = -1;
while(i < lent){
if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; }
else j = next[j];
}
}
//一次匹配,从st到ed-1位置,默认位置为st=0,ed=lens
int indexMP(int st,int ed){
int i = st , j = 0;
while(i < ed && j < lent){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
}
if(j >= lent) return i-lent;
else return -1;
}
//多次匹配(可重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP(int st,int ed){
int i = st , j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = next[j]; save[ns++] = i-lent; }
}
return ns;
}
//多次匹配(不重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP__(int st,int ed){
int i = st,j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = 0; save[ns++] = i-lent; }
}
return ns;
}

//在t串内统计每个前缀的个数,改写getNext数组
int countPrefix_T(){
memset(cnt,0,sizeof(cnt));
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1) ++i , ++j;
else if(t[j] == t[i]) cnt[j]++ , ++i , ++j , next[i] = j;
else j = next[j];
}
for(int i = len; i > 1; i--)
cnt[next[i]-1] += cnt[i-1];
int sum = 0;
for(int i = 0; i < len; i++){
cnt[i]++;
sum += cnt[i];
sum %= MOD;
}
//for(int i = 0; i < len; i++)
// printf("%d : %d\n",i,cnt[i]);
return sum;
}

//在s串中统计t串每个前缀的个数
//cnt[i] 表示 t[0~i]这个子串在s中出现的次数
void countPrefix_S(int *cnt){
for(int i = 0 ; i <= lent; i++) cnt[i] = 0;
int i = 0 , j = 0;
while(i < lens){
if(j == -1) { ++i; ++j; }
else if(s[i] == t[j]) { cnt[j]++; ++i; ++j; }
else j = next[j];
}
for(int i = lent; i > 1; i--)
cnt[next[i]-1] += cnt[i-1];
}
};