kmp-白红宇

kmp

阅读量：4493 次

发布时间：2019-06-08

本文共 1579 字，大约阅读时间需要 5 分钟。

还真是写了又忘忘了再写......

kmp算法用于加速字符串的匹配，优化暴力匹配

文本串 s "abcaabcabeabcabd"

模式串 t "abcabd"

t 匹配 s，找 t 在 s 中出现的最早位置

暴力匹配试试

指针i，j 从0开始右移匹配

abcaabcabeabcabd

abcabd

此时 s [ i ] 和 t [ j ] 不匹配，j 跳到 0 继续匹配，但这样很耗时间

瞎搞一下，发现 t [ j ] 前面的都已经和 s [ i ] 前面的匹配好了，这样如果 j 前面子串的前缀和后缀相同的最大长度都可以不用匹配

e.g. （1） t 串中 abcab的最后一位 t [ 4 ] b 不匹配，前面的abca都匹配好了，即 s [ 3 ] = t [ 3 ] =a， t [ 3 ] a是后缀， t [ 0 ] a 是和其相等的前缀，肯定和 s [ 3 ] 相等

这位就可以不用匹配了

直接跳到 t [ 1 ] 去匹配

更具象一点

（2）abcaabcabeabcabd

abcabd

此时 s [ i ] 与 t [ j ] 不匹配，后缀 t [ 3 ] t [ 4 ] = ab 与 s [ 7 ] s [ 8 ] = ab 匹配好了，最大前缀 t [ 0 ] t [ 1 ] = ab 肯定也匹配好了

接下来 j 直接跳到 2 与 s [ 9 ] 匹配就可以了

我们用一个数组nxt表示 t 串中位置 i 不匹配时该跳到哪一位

线性求nxt数组，根据最大前后缀匹配求（找个串模拟一下更好理解

void getnxt(string s){    ll n=s.size();    ll j=0, k=-1; //j比k大一位 　　 nxt[0]=-1; //初始化为-1， 方便判断 　　 while(j

nxt数组优化

在e.g.（1）中，

abcaabcabeabcabd

abcabd

j=4

t [ 4 ]不匹配， nxt [ 4 ]=1，j 应该跳到1去匹配，但是 t [ 1 ] == t [ 4 ]， t [ 4 ]失配， t [ 1 ]肯定也失配

这样就又多耗时间了

咋优化咧

在求 nxt 的时候判断一下就好啦

void getnxt(string s){    ll n=s.size();    ll j=0, k=-1; //j比k大一位　　 nxt[0]=-1; //初始化为-1， 方便判断　　 while(j

完整kmp代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;typedef long long ll;typedef pair
                 
                   P;typedef long double ld;#define mem(x) memset(x, 0, sizeof(x))#define me(x) memset(x, -1, sizeof(x))#define fo(i,n) for(i=0; i
                  
                   >s>>t) { getnxt(t); n=s.size(); m=t.size(); k=kmp(s,t); cout<
                   
                    <

转载于:https://www.cnblogs.com/op-z/p/11307464.html

你可能感兴趣的文章