KMP模板

发布于 2017-11-25  366 次阅读


题目描述

算法介绍

KMP是一种字符串匹配算法,可以求出一个字符串在另一个字符串中出现的次数。
时间复杂度为$ O(N+M) $

算法实现

算法分为预处理next数组和查询两步进行。

预处理

next数组表示从起始位置到当前位置最长的前缀和后缀的长度
那么,在处理时,我们就拿当前位置和原来匹配的最长前缀的后一位比较
如果相同,那么长度+1
也就有$next[j] = next[j-1]+1$

如果不相同,那么根据此数组的性质,显而易见,你的相等的部分只能向前找
也就是说,你的这个位置的next值会减小
也就是去原来的最长相等前缀去找

所以,我们可以得到next数组的求解方法:
每一次检查上一次最长前缀的后一个位置
如果相等则$next[j]=next[i]+1$
否则令$i=next[i-1]+1$,继续循环匹配
其实这就是自己匹配自己的过程。
这是最难理解的地方,多手算几遍就好了

查询

本算法难在于next预处理,如果你已经懂了,就很简单了
我们设定两个指针i,j,指向两个字符串。
如果$i == j $那么$ i++,j++$
如果失配,就令$i = next[i-1]+1$
是不是很简单

源代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

char str1[1000005],str2[1000005];
//str1是被匹配字符串,str2是匹配字符串
int Next[1000005];
vector <int> Ans;

inline void init(char *str){ //对字符串进行预处理
    int len,t;
    len = strlen(str);
    Next[0] = -1;
    for(int i = 1;i < len;i++){
        t = Next[i-1];
        while(str[t+1] != str[i] && t >= 0)
            t = Next[t];
        if(str[t+1] == str[i])
            Next[i] = t+1;
        else
            Next[i] = -1;
    }
}

void kmp(char *str1,char *str2){ //kmp查找
    init(str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int i = 0,j = 0;
    while(j < len1){
        if(str2[i] == str1[j]){  //相同
            i++;j++;
            if(i == len2){
                Ans.push_back(j-len2+1);
                i = Next[i-1]+1;
            }
        }
        else{  //失配,根据next数组寻找下一个位置
            if(i == 0)
                j++;
            else
                i = Next[i-1] + 1;
        }
    }
}

int main(){
    cin >> str1 >> str2;
    int l = strlen(str2);
    kmp(str1,str2);
    for(int i = 0;i < Ans.size();i++)
        printf("%d%c",Ans[i],'\n');
    for(int i = 0;i < l;i++){ //洛谷题目需要的输出next数组
        printf("%d ",Next[i] + 1);
    }
    return 0;
}

一个OIer。