字符串匹配算法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++

include<iostream>

include<string.h>

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;

}

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据