lps数组

longest prefix and suffix 简称 lps
lps数组用来存放模式串pat对应子串的最大相同前后缀的长度。
lps代码实现：

void get_lps(char* pat,int* lps)
{
   int m = strlen(pat);
   int j, i;
   j = 0; 
   i = 1;
   lps[0] = 0;
   while(i < m)
   {
   if(pat[i] == pat[j])
    {  
       j++;
       lps[i] = j;
       i++;
    } else{
             if(j != 0){
             j = lps[j-1];
             }else{
             lps[i] = 0;
             i++;        
          }
   }
}
for (i = 0;i < m; i++)
{
printf("%d",lps[i]);
if(i < m-1)
printf(" ");
}
printf("\n");

next数组

根据lps求出next数组：
将next[0] = -1,然后将lps放入
next代码实现：

void get_next(char* pat,int* lps){
int m = strlen(pat);
get_lps(pat,lps);
int i;
next[0] = -1;

for(i = m - 2; i >= 0 ; i--){
lps[i+1] = lps[i];}
lps[0]= -1;
for(i=0;i<m;i++)
{
  printf("%d",lps[i]);
  if(i<m-1)
    printf(" ");
}
}

KMP 的实现

int kmpsearch(char* s,char* t,int* next)
{
    get_next(t,next);
    int slen = strlen(s);
    int tlen = strlen(t);
    int i=0,j=0;
    while(i < slen && j < tlen)
    {
        if(j == -1 || s[i] == t[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == tlen)
    {
        return i-tlen;
    }
    else
        return -1;
}

改进KMP算法

关键在于模式串的回溯，求一种方法可以一步到位（元叔：期末我们再来讲解）

在实际应用中，KMP算法并不比暴力匹配算法快很多，改进KMP算法更是如此

2019.10.17 数据结构课堂笔记