字符串-KMP算法


描述

字符串匹配的问题可以大致描述为:给定主串S(Source,长度为n),模式串P(Pattern,长度为m),要求查找出P在S中出现的位置。最常见的做法的是暴力查找,linux的string.h中使用的就是:

char * strstr(register const char *s, register constchar *wanted)
{
     register const size_t len = strlen(wanted);
     if (len ==0) return (char*)s;
     while (*s !=* wanted || strncmp(s, wanted, len))
         if (*s++=='\0')
             return (char*)NULL;
     return (char*)s;
}

该算法的复杂度是S_len * P_len。而KMP算法就是一种更好的算法,利用每次匹配的结果,尽量避免重复进行不可能位置的匹配,快速的向右移动查找结果。

KMP算法

KMP算法的主要思想是保持主串S向右移动不变,不断的回溯模式串P KMP

主串S在位置D匹配失败,如果此时回溯模式串P的话,那么究竟移动多少其实需要看模式串的特征,即已匹配有效的部分是[ABCDAB]D括号中的部分,由于D位置不匹配,匹配串右移,[ABCDAB]移动成[AB]CDAB才能停下来。由于前面是已经匹配的部分,而移动的又是模式串,移动的模式串的过程其实是模式串前缀和模式串后缀匹配的过程,即: KMP

  • 模式串移动位数 = 已匹配的模式串位数 - 模式串中前缀和后缀最大公共长度

前缀和后缀最大公共长度

该部分的思想较为简单,其实是根据P[0…i]求P[i+1]的长度的问题,详细算法见下图。 KMP