字符串匹配算法KMP算法

字符串匹配算法——KMP 算法
一、算法介绍：
KMP 算法是一种改良的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因而人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。
KMP 算法的外围是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到疾速匹配的目标。
具体实现就是通过一个 next()函数实现，函数自身蕴含了模式串的部分匹配信息。
二、算法具体分析：
1、写出字符串前缀；
2、找出每个前缀字符串的最长公共前后缀；
3、写出前缀表 prefix table；
4、依据前缀表进行匹配。
三、例子：
T：a b a a c a b a b c a c
P：a b a b c
首先写出字符串 P 的前缀如下：

                最长公共前后缀长度            前缀表

a 0 -1
a b 0 0
a b a 1 0
a b a b 2 1
a b a b c 0 2
而后依据前缀表进行匹配：

T：a b a a c a b a b c a c

0 1 2 3 4 数组下标
P：a b a b c
-1 0 0 1 2 前缀表：当不匹配的时候将对应下标的字母挪动到以后比拟的地位。

过程：

T：a b a a c a b a b c a c
√ √ √ ×

0 1 2 3 4 数组下标
P：a b a b c
-1 0 0 1 2

此时 a 与 b 不匹配，能够看到前缀表里 b 所对应的是 1，也就是将数组下标为 1 的字母 b 挪动到以后地位进行比拟如下：

T：a b a a c a b a b c a c

   √ ×
   0 1 2 3 4 数组下标
P：a b a b c
  -1 0 0 1 2

此时 a 和 b 还是不匹配，那么持续将下标为 0 的挪动到以后地位如下：

T：a b a a c a b a b c a c

     √ ×
     0 1 2 3 4 数组下标
  P：a b a b c
    -1 0 0 1 2

又不匹配继续移动：

T：a b a a c a b a b c a c

       ×
       0 1 2 3 4 数组下标
    P：a b a b c
      -1 0 0 1 2

不匹配继续移动：（- 1 的地位就是 P 串的 a 的后面一个地位，为空字符）

T：a b a a c a b a b c a c

         √ √ √ √ √    —匹配胜利
         0 1 2 3 4 数组下标
      P：a b a b c
        -1 0 0 1 2

此时咱们匹配到了一个残缺的字符串，然而并没有完结，可能前面的字符串中还有可能匹配到的，所以此时继续移动，将下标为 2 的字符挪动到以后地位：

T：a b a a c a b a b c a c

             0 1 2 3 4 数组下标
          P：a b a b c
            -1 0 0 1 2

因为 c 和 a 不匹配所以咱们的匹配完结，不必持续往后比拟了，完结。

四、代码实现：
c++

using namespace std;

/*
pattern[]字符串
prefix[] 前缀表
n 字符串长度
*/
void prefix_table(char pattern[],int prefix[],int n) {

prefix[0] = 0;
int len = 0;
int i = 1;
while (i<n) {if (pattern[i] == pattern[len])
    {
        len++;
        prefix[i] = len;
        i++;
    }
    else
    {if (len > 0)
        {len = prefix[len - 1];
        }
        else
        {prefix[i]= len;
            i++;
        }
    }
}

}

void move_prefix_table(int prefix[],int n) {

int i;
for (i = n - 1; i > 0;i--) {prefix[i] = prefix[i-1];
}
prefix[0] = -1;

}

void kmp_search(char text[],char pattern[],int p,int t) {

int n = p;
int *prefix = (int*)malloc(n * sizeof(int));
prefix_table(pattern,prefix,n);
move_prefix_table(prefix,n);
cout << "the prefix_table is";
for (int k = 0; k < n;k++) {cout << prefix[k]<<" ";
}
cout << endl;
/* 规定
text[i]    ,        len(text)=m
pattern[j]    ,    len(pattern)=n
*/
int i = 0;
int j = 0;
int m = t;
while (i<m) {if (j == n - 1&&text[i]==pattern[j] )
    {
        cout << "Found pattern,the position is" << i-j;
        j = prefix[j];    
    }
    if (text[i] == pattern[j])
    {
        i++;
        j++;
    }
    else
    {j = prefix[j];
        if (j==-1) {
            i++;
            j++;
        }
    }
}

}

int main() {

char pattern[] = "abba";
char text[] = "abbbbabbcabbab";
int p_len = strlen(pattern);
int t_len = strlen(text);
kmp_search(text,pattern, p_len, t_len);
return 0;

}

字符串匹配算法KMP算法

include<iostream>

include<string.h>