KMP算法笔记

【简述】：

kmp算法：
1 kmp是用来匹配字符串，只能够匹配单一的字符串
2 kmp的算法的过程：
1：假设文本串的长度为n，模式串的长度为m；
2：先例用O(m)的时间去预处理next数组，next数组的意思指的是当前的字符串匹配失败后要转到的下一个状态；
3：利用o(n)的时间去完成匹配；

3 时间复杂度为o(n+m)即o(n)；

【例题】：

1. 可重叠匹配：j=nxt[j]

求模式串在主串中出现的次数，可重叠【HDU 1686 Oulipo】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E4+7;
string a,b;
int ans;
int nxt[N];
void getnxt( int n)
{
    int i = 0;
    int j = -1;
    nxt[0] = -1;
    while (i<n)
        if (j==-1||b[i]==b[j]) nxt[++i]=++j;
    else j = nxt[j];
}
void kmp( int n,int m)
{
    int i = 0 ;
    int j = 0 ;
    getnxt(m);
   // for ( int i = 0 ; i < m ; i++) cout<<i<<" "<<nxt[i]<<endl;
    while (i<n)
    {
        if (j==-1||a[i]==b[j]) i++,j++;
        else j = nxt[j];
        if (j==m) ans++,j=nxt[j];
    }
}
int main()
{

        ios::sync_with_stdio(false);
        int T;
        cin>>T;
        while (T--)
        {
            cin>>a>>b;
            swap(a,b);
            int la = a.length();
            int lb = b.length();
            ans = 0 ;
            kmp(la,lb);
            cout<<ans<<endl;
        }

    return 0;
}

可重叠匹配

问模式串在文本串中出现的次数，不允许重叠【HDU 2087 剪花布条】

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <deque> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E4+7; string a,b; int ans; int nxt[N]; void getnxt( int n) { int i = 0; int j = -1; nxt[0] = -1; while (i<n) if (j==-1||b[i]==b[j]) nxt[++i]=++j; else j = nxt[j]; } void kmp( int n,int m) { int i = 0 ; int j = 0 ; ans=0; getnxt(m); // for ( int i = 0 ; i < m ; i++) cout<<i<<" "<<nxt[i]<<endl; while (i<n) { if (j==-1||a[i]==b[j]) i++,j++; else j = nxt[j]; if (j==m) ans++,j=0; } } int main() { ios::sync_with_stdio(false); while(cin>>a>>b) { ans=0; if(a[0]=='#'||b[0]=='#') break; int len1=a.size(); int len2=b.size(); kmp(len1,len2); printf("%d ",ans); } return 0; }

#include<stdio.h> #include<string.h> #define N 1000005 int next[N],a[N],b[N]; int m,n; void Next()//就是上面的分匹配表的实现 { int i,j; i=0; j=-1; next[i]=j; //匹配表初值 while(i<m) { if(j==-1||b[i]==b[j]) { i++; j++; next[i]=j; } else j=next[j]; } return ; } int KMP()//kmp匹配算法 { int i,j; i=j=0; Next();//先计算部分匹配表 while(i<n) { if(j==-1||a[i]==b[j]) { i++; j++; if(j==m) return i-m+1;//找到目标字符串，返回到主程序。 } else j=next[j];//a[i]与b[j]不匹配，查表需要跳过的字符个数。 } return -1;//没有找到返回-1 } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) scanf("%d",&a[i]); for(int i=0; i<m; i++) scanf("%d",&b[i]); printf("%d ",KMP()); } return 0; }

来自于其他人的做法： •知识点：KMP算法、对next数组的理解 •KMP算法中next数组的含义是什么？ •next数组：失配指针 •如果目标串的当前字符i在匹配到模式串的第j个字符时失配，那么我们可以让i试着去匹配next(j) •对于模式串str，next数组的意义就是： •如果next(j)=t,那么str[1…t]=str[len-t+1…len] •我们考虑next(len)，令t=next(len); •next(len)有什么含义？ •P [吨1 ...] = P [称为T-1 ...仅] •那么，长度为len-next(len)的前缀显然是符合题意的。 •接下来我们应该去考虑谁？ •t = next（next（len））; •t = next（next（next（len）））; • 一直下去直到t=0,每个符合题意的前缀长是len-t

相关推荐