KMP,额

Posted by Cww97 on 2016-07-29

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52060449
容易理解不过我没用这个代码的讲解

非常清真的讲解

KMP中级题目汇总

hdu1711

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
//hdu1711 cww97
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1000007;
int Next[N],n,m,a[N],b[N];

void GetNext(int m){
int i=0,j=-1;
Next[0]=-1;
while (i<m){
if (j==-1||b[i]==b[j]){
if (b[++i]!=b[++j])Next[i]=j;
else Next[i]=Next[j];
}else j=Next[j];
}
}

int kmp(int n,int m){
int i=0,j=0;
GetNext(m);
while (i<n&&j<m){
if (j==-1||a[i]==b[j])i++,j++;
else j=Next[j];
if (!i&&!j)break;
}
if (j==m)return i-m+1;
else return -1;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
while (T--){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for (int i=0;i<n;i++)scanf("%d",&a[i]);
for (int i=0;i<m;i++)scanf("%d",&b[i]);
if (n<m)puts("-1");
else printf("%d\n",kmp(n,m));
}
return 0;
}

hdu2203

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
//hdu 2203 cww97
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=100007;
char st1[N],st2[N];
int Next[N];

void GetNext(char *a){
int i=0,j=-1,len=strlen(a);
Next[0]=-1;
while (i<len){
if (j==-1||a[i]==a[j]){
if (a[++i]!=a[++j])Next[i]=j;
else Next[i]=Next[j];
//printf("%c: %d\n",a[i],next[i]);
}else j=Next[j];
}
}

bool kmp(char *a,char *b){
int A=strlen(a),B=strlen(b),i=0,j=0;
GetNext(b);
while (i<A&&j<B){
if (j==-1||a[i]==b[j])i=(i+1)%A,j++;
else j=Next[j];
if (!i&&!j)break;
}
return j==B;
}

int main(){
//freopen("fuck.in","r",stdin);
while (cin>>st1>>st2){
int l1=strlen(st1),l2=strlen(st2);
if (l1<l2)puts("no");
else{
if (kmp(st1,st2))puts("yes");
else puts("no");
}
}
return 0;
}

hdu3336

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
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200007,P=10007;
int n;
char a[N];
int f[N],next[N];

void getNext(){
int i=0,j=-1;
next[0]=-1;
while (i<n){
if (j==-1||a[i]==a[j]){
//if (a[++i]!=a[++j])next[i]=j;
//else next[i]=next[j];
next[++i]=++j;
//printf("next[%d]=%d\n",i,next[i]);
}else j=next[j];
}
}

int main(){
//freopen("fuck.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d\n",&n);
for (int i=0;i<n;i++)scanf("%c",&a[i]);
getNext();
int ans=0;
memset(f,0,sizeof(f));
for (int i=1;i<=n;i++){
//if (next[i]<=0)f[i]=1;
//else
f[i]=(f[next[i]]+1)%P;
//printf("f[%d]=%d\n",i,f[i]);
ans=(ans+f[i])%P;
}
printf("%d\n",ans);
}
return 0;
}

hdu5763,2016多校第四场
题解
这孩子居然暴力过了,数据有毒

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
/*令dp[i]表示到i结尾的字符串可以表示的不同含义数,那么考虑两种转移:
末尾不替换含义:dp[i - 1]
末尾替换含义:dp[i - |B|] (A.substr(i - |B| + 1,|B|) = B)
那么对于末尾替换含义的转移,需要快速判断BB能不能和当前位置的后缀匹配,kmp或者hash判断即可。
复杂度:O(N)*/
//cww97
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100007;
const int P=1000000007;
char a[N],b[N];
bool mat[N];
int next[N];
ll f[N];

void getNext(int m){
int i=0,j=-1;
next[0]=-1;
while (i<m){
if (j==-1||b[i]==b[j]){
if (b[++i]!=b[++j])next[i]=j;
else next[i]=next[j];
}else j=next[j];
}
}

void KMP(int n,int m){
memset(mat,0,sizeof(mat));
int i=0,j=0;
getNext(m);
while (i<n&&j<m){
if (j==-1||a[i]==b[j])i++,j++;
else j=next[j];
if (!i&&!j)break;
if (j==m){
mat[i]=1;
//printf("mat[%d]get\n",i);
j=next[j];
}
}
}

int main(){
freopen("fuck.in","r",stdin);
int T;
scanf("%d\n",&T);
for (int cas=1;cas<=T;cas++){
scanf("%s%s",a,b);
int n=strlen(a);
int m=strlen(b);
KMP(n,m);
memset(f,0,sizeof(f));
f[0]=1;
for (int i=1;i<=n+1;i++){
if (mat[i])f[i]=(f[i-m]+f[i-1])%P;
else f[i]=(f[i-1])%P;
//printf("f[%d]=%d\n",i,f[i]);
}
printf("Case #%d: %I64d\n",cas,f[n]%P);
}
return 0;
}