JZTXT

kmp

发布时间 2023-03-24 09:40:01作者: 哎呦哎(iui)

 

1.模板题：


给定两个数字序列 a[] 和 b[]，b[] 有可能整体作为一个连续子序列出现在了 a[] 中，现在请你找出 b[] 在 a[] 中第一次出现的位置（起始位置从 1 开始计数），如果一次都没有出现，请输出 -1。

输入格式


第一行包含一个数字 T，表示测试用例的个数。
对于每组测试用例，第一行包含两个数字 n m ( 1<= n <= 1000000, 1 <= m <= 10000 )，表示 a[] 和 b[] 的长度。
接下来的一行包括 n 个数字，依次表示 a[1], a[2], a[3] ... a[n]，-1000000 <= a[i] <= 1000000 
接下来的一行包括 m 个数字，依次表示 b[1], b[2], b[3] ... b[m]，-1000000 <= b[i] <= 1000000

输出格式


对于每组数据输出一行，请输出 b[] 整体作为一个连续子序列在 a[] 中的首次出现位置的起始下标，如果一次都没有完整出现，输出 -1。

样例输入


2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

样例输出


6
-1

样例解释


对于第一组数据，1 2 1 2 3 [1 2 3 1 3] 2 1 2，首次出现位置的起始下标为 6。
对于第二组数据，b[] 没有出现在 a[] 中，输出 -1。

 

 

#pragma GCC optimize(2)
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
typedef long long ll;
ll read(){
    ll x=0; ll f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
using namespace std;
const int maxn=5e6+100;
int s[maxn];
int p[maxn];
int ne[maxn];
int n,m;
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<m){
        if(k==-1||p[j]==p[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int kmp(){
    int i=0,j=0;
    getnext();
    while(i<n){
        if(j==-1|s[i]==p[j]){
            i++;
            j++;
        }
        else{
            j=ne[j];
        }
        if(j==m){
            return i;
        }
    }
    return -1;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>s[i];
        } 
        for(int i=0;i<m;i++){
            cin>>p[i];
        }
        if(kmp()==-1){
            cout<<-1<<endl;
        }
        else{
            cout<<kmp()-m+1<<endl;
        }
    }
}

 

2.传送门

求模式串在待匹配串中的出现次数。

Input

第一行是一个数字T，表明测试数据组数。之后每组数据都有两行：
第一行为模式串，长度不大于10,000；
第二行为待匹配串，长度不大于1,000,000。（所有字符串只由大写字母组成）

Output

每组数据输出一行结果。

Sample Input

4
ABCD
ABCD
SOS
SOSOSOS
CDCDCDC
CDC
KMP
SOEASY

Sample Output

1
3
0
0
这个题是出现次数例如：

这个是出现了几次例如
aa
aaaa
这个是三次

下一个题和这一个不一样

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
/*
这个是出现了几次例如
aa
aaaa
这个是三次 
*/ 
const int maxn=1e6+100;
char a[maxn];
char b[maxn];
int ne[maxn];
int lena,lenb;
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int kmp(){
    int i=0,j=0;
    int ans=0;
    getnext();
    while(j<lenb){
        if(i==-1||a[i]==b[j]){
            i++;
            j++;
        }
        else{
            i=ne[i];
        }
        if(i==lena){
            //i=ne[i];
            ans++;
        }
    }
    return ans;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        scanf("%s%s",a,b);
        lena=strlen(a);
        lenb=strlen(b);
        cout<<kmp()<<endl; 
    }
}

 

剪布条

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？ 

Input输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。 
Output输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。 
Sample Input

abcde a3
aaaaaa  aa
#

Sample Output

0
3
这个题和上一个不一样：

这个就是不能重复
例如：
aa
aaaa 为2
aa
aaaaaa 为3 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
/*
这个就是不能重复
例如：
aa
aaaa  为2
aa
aaaaaa 为3 
*/
char a[maxn];//长串 
char b[maxn];//短串 
int ne[maxn];
int lena,lenb;
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int kmp(){
    int i=0,j=0;
    int ans=0;
    getnext();
    while(j<lenb){
        if(i==-1||a[i]==b[j]){
            i++;
            j++;
            if(i==lena){
                ans++;
                i=0; 
            }
        }
        else{
            i=ne[i];
        }
        
    }
    return ans;
}
int main(){
    while(~scanf("%s",b)){
        if(b[0]=='#'){
            break; 
        }
        scanf("%s",a); 
        lena=strlen(a);
        lenb=strlen(b);
        cout<<kmp()<<endl;    
    } 
}

 

next数组的应用

1.传送门

WenDavid喜欢周期循环，看到不是周期循环的字符串就很不爽。
现在WenDavid得到一个字符串，可以在字符串末尾添加若干字符，请你帮WenDavid想想，最少添加多少个字符，才能使得字符串变得周期循环（即至少出现两个循环节）。

Input

第一行是一个整数 T ( 0<T<=100 ) 代表测试数据的组数。
之后T行每行一个字符串，由小写字母组成，字符串的长度3<=L<=100000。

Output

每组数据输出一行结果。

Sample Input

3
ppp
pip
machinelearning

Sample Output

0
1
15

循环节长度

int m=len-Next[len];
if(len%m==0)//这个是代表是不是真好够整个循环
cout<<m <<endl; //每个循环节的长度
cout<<len/m<<endl; //循环几次

解析：

m=lena-ne[lena]，这个是循环节，
lena%m==0&&lena/m>=2这个是说正好是一个循环，并且循环长度大于2
m-lena%m//是补充几个构成循环

 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena,lenb;
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        scanf("%s",a);
        lena=strlen(a);
        getnext();
        int ans=0;
        int m=lena-ne[lena];//循环节 
        if(lena%m==0&&lena/m>=2){//至少右一个循环节 
            cout<<0<<endl;
        } 
        else{
            cout<<m-lena%m<<endl;
        }
    }
}

判断循环节和一个循环

传送门

cgg给你一个字符串s,问在所有的[0, i]区间是否有完整的循环节,若有,输出i并输出循环次数。（嗯哼，就是这么简单的题意）

Input

输入包含多组样例。
每组数据两行，第一行一个整数n（2<=n<=1000000）,为字符串的长度，第二行包含一个字符串。
数据以单个0结尾

Output

对于每个测试用例，在一行上输出“ Test case＃”和连续的测试用例编号； 
然后，对于长度为i且循环次数K> 1的每个前缀，输出前缀大小i和以单个空格分隔的循环次数K； 前缀大小必须按升序排列。 在每个测试用例之后打印空白行。

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4
判断是不是一整个循环
int p=i-ne[i];
if(i%p==0&&ne[i]!=0){
       cout<<i<<" "<<i/p<<endl;
}

 

 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena; 
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int main(){
    int kase=1;
    while(cin>>lena&&lena){
        scanf("%s",a);
        getnext();
        printf("Test case #%d\n",kase++);
        for(int i=1;i<=lena;i++){
            int p=i-ne[i];
            if(i%p==0&&ne[i]!=0){
                cout<<i<<" "<<i/p<<endl;
            }
        }
        cout<<endl; 
    }
}

输出循环次数：

传送门

给定若干个长度 ≤ 1000000 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。

输入格式

输入若干行，每行有一个字符串，字符串仅含英语字母。
输入数据以"."结束。

输出格式

对于每组输入数据输出一行，找出每个字符串最多是由多少个相同的子字符串重复连接而成的。

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena; 
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int main(){
    while(scanf("%s",a)){
        if(a[0]=='.'){
            break;
        }
        lena=strlen(a);
        getnext();
        int ans=1;
        int p=lena-ne[lena];
        if(lena%(lena-ne[lena])==0){
            ans=lena/(lena-ne[lena]);
        }
        cout<<ans<<endl;
    }
}

 

传送门

题意：一个字符串，求符合EAEBE形式情况下最大E子串的长度

思路：前缀E和后缀E可以用next数组求出，然后在判断中间的E是否存在，具体做法是：next[len]=i，在[2 * i ,len - i](因为不能重合)内找是否有next[j]=i，存在则i就为答案，不存在的话令i=next[i],而不是i--，继续找
这个题不理解的话可以自己画一下

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e6+100;
char a[maxn];
int ne[maxn];
int lena; 
void getnext(){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<lena){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else{
            k=ne[k];
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        scanf("%s",a);
        lena=strlen(a);
        getnext();
        int ans=0;
        for(int i=ne[lena];i;i=ne[i]){//就是缩小公共前后缀
            for(int j=i*2;j<=lena-i;j++){
                if(ne[j]==i){/说明和开头一样
                    ans=i;
                    break;
                }
            }
            if(ans){
                break;
            }
        } 
        cout<<ans<<endl;
    }
}

 

 

传送门

 

就是找一个k和p,让去掉前k个字母剩下的形成的循环节为p,让求k+p最小的情况下k最小

这个题就是把字符串反转然后再求

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=1e6+100;
int a[maxn];
int b[maxn];
int ne[maxn];
void getnext(int l){
    int j=0,k=-1;
    ne[0]=-1;
    while(j<l){
        if(k==-1||a[j]==a[k]){
            j++;
            k++;
            ne[j]=k;
        }
        else
            k=ne[k];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    for(int i=0,j=n-1;i<n;i++,j--){
        a[i]=b[j];
    }
    getnext(n);
    int z=0x3f3f3f3f;
    int ans1=0;
    int ans2=n-ne[n];
    for(int i=1;i<=n;++i){
        int k=n-i;
        int p=i-ne[i]; 
        if(k+p<z){
            z=k+p;
            ans1=k;
            ans2=p;
        }
        else if(k+p==z&&ans2>p){
            ans1=k;
            ans2=p;
        }
    }
    printf("%d %d\n",ans1,ans2);
}