Data Structure Design of KMP

KMP

朴素字符串匹配方法：

前缀函数定义

给定一个长度为$n$的字符串$s$，其 前缀函数$\pi[i]$被定义为一个长度为$n$的数组 。 其中$\pi[i]$的定义是：

1. 如果子串$s[0…i]$有一对相等的真前缀与真后缀：$s[0…k-1]$和$s[i-(k-1)…i]$,namo有 ，$\pi[i]$就是这个相等的真前缀（或者真后缀，因为它们相等：)）的长度，也就是$\pi[i]=k$；
2. 如果不止有一对相等的，那么$\pi[i]$就是其中最长的那一对的长度；
3. 如果没有相等的，那么$\pi[i]=0$。

简单来说$\pi[i]$就是，子串$s[0…i]$最长的相等的真前缀与真后缀的长度。

用数学语言描述如下：

$\pi[i]=max_{k=0…i}\{k:s[0…k-1]\}=s[i-(k-1)…i]$

特别地，规定$\pi[0]=0$。

Next数组求解：

改进后的KMP算法：

模板1：

//求ne数组，考察前面那个，如果后一个可以匹配就+1，否则退到ne[j]
for(int i=2,j=0;i<=n;i++){
    while(j&&p[i]!=p[j+1])j=ne[j];
    if(p[i]==p[j+1]) j++;
    ne[i]=j;
}

//KMP匹配
for(int i=1,j=0;i<=m;i++){
    while(j&&s[i]!=p[j+1]) j=ne[j];  //j不停回溯直到j为第一位而且第二位还不与i匹配
    if(s[i]==p[j+1]) j++;  //如果可以匹配，则j往前走一位
    if(j==n){
        //匹配成功
        printf("%d ",i-j);
    }
}

模板2：

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

KMP的优化

2.1.3 KMP算法中$next[]$数组的优化

​ 我们观察我们在匹配的过程中，假如在$j$位置失配了，模式串必然会跳到其对应$j=next[j]$处，但是 由于在构$next[]$造的时候若有此时则$p[j]=p[next[j]]$需要再次递归，即令$next[j]=next[next[j]]$，因此在$next[]$构造的时候若有模式串$p[j]=p[next[j]]$则令$next[j]=next[next[j]]$即可

课程设计源码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define bool int
#define true 1
#define flase 0
#define MAXN 20510
#define N 2010

char str[MAXN];                                     //待匹配全文
char word[N];                                       //目标匹配字符串
char string[MAXN];                                  //临时字符串
int len[MAXN];                                      //记录每个单词的长度 
int n,m;                                            //n为整文长度
int ans[MAXN],cnt=0,length;                         //答案数组，从0开始统计匹配字符串的个数和位置
int ne[MAXN];                                       //next[]数组，存储目标单词的最长前缀串的位置

void init()
{
    memset(ans, 0, sizeof ans);
    cnt = 0;
}

void read()
{
    scanf("%[^\n]", str + 1);                       //读入文章（一行）
    n = strlen(str + 1);                            //统计文章长度
    
    m = 1;
    while(str[m] != ' ')                            //获取开头的待匹配单词
    {
        word[m] = str[m];
        m ++;
    }
    -- m;

    m = strlen(word + 1);

    printf("The definition word: %s\n", word + 1);
    puts("=============================================\n");
}

void print(){
    printf("\nThere are %d words in the article which is same with the definition word %s.\n",cnt,word);
    
    if(cnt != 0)
    {
        printf("\nThe positions are:\n");
        for(int i = 1;i <= cnt; ++ i)
        {
            printf("%d ", ans[i]);
            if(i == cnt)
            {
                printf("\n");
            }
        }
    }
    puts("");
    puts("=============================================\n");
}

void NAIVE_STRING_MACHINE(){
    for(int i = m + 1; i <= n; ++ i)                //对字符串进行朴素匹配
    {
        bool flag = true;
        for(int j = 1, k = i; k <= n && j <= m ; ++ j, ++ k)
        {
            if(str[k] != word[j]) 
            {
                flag = false;
                break ;
            }    
        }
        
        if(flag)
        {
            ans[++ cnt] = i - m - 1;
        }
    }
}

void next(){                                        //next[]数组正常求解法
    memset(ne, 0, sizeof ne);
    
    int i, j;                                   
    for(i = 2, j = 0;i <= m; i ++)                  //预处理p的最长前缀串-> next[]数组
    {
        while(j && word[i] != word[j+1])
        {
            j = ne[j];
        }
        if(word[i] == word[j+1]) 
        {
            j ++;
        }

        ne[i] = j;
    }    
}

void next_fast(){
    memset(ne, 0, sizeof ne);
    
    int i, j, k;                                   
    for(i = 2, j = 0 ; i <= m ; i++)
	{ 
		if(word[i] == word[j])
		{	
            ne[i] = ne[j];
        }    
		else
		{	
            ne[i] = j;
        }    
		while(j > 0 && word[i] != word[j])
		{
			j = ne[j-1];
		}
		if(word[i] == word[j])
		{
			j ++;
		}
	}
}

void KMP()                                          //KMP字符串匹配
{       
    int i , j;

    for(i = m + 1, j = 0;i <= n;i ++)
    {
        while(j && str[i] != word[j+1])             //求ne数组，考察前面那个，如果后一个可以匹配就+1，否则退到ne[j]
        {
            j = ne[j];                              //j不停回溯直到j为第一位而且第二位还不与i匹配
        }
        
        if(str[i] == word[j+1]) j++;                //如果可以匹配，则j往前走一位
        
        if(j == m)
        {
                                                    //匹配成功
            ans[++ cnt] =  i - j + 1 - m - 1;
        }
    }
}

void work1()                                        //对全文进行朴素匹配
{         
    init();                                         //初始化                    
    printf("Below is the NAIVE_STRING_MATCHING Algorithm...\n\n");      
    
    NAIVE_STRING_MACHINE();

    print();
}

void work2()
{                            
    init();
    printf("Below is the KNUTH_MORRIS_PRATT Algorithm...\n\n"); 
    
    next();   
    KMP();

    print();    
}

void work3(){
    init();
    printf("Below is the KNUTH_MORRIS_PRATT Algorithm with faster next[] caculating...\n\n"); 

    next_fast();
    KMP();

    print();
}

int main(){
//==================================

    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);    
//#endif 
//==================================
    //读入全文和待匹配单词
    read();                             
    //基于朴素字符串匹配的算法
    work1();
    //KMP字符串匹配算法
    work2();
    //扩展KMP字符串匹配算法
    work3();
    return 0;
}