字符串-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

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

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

前缀和后缀最大公共长度

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


本文作者 ： cyningsun

本文地址 ： https://www.cyningsun.com/04-04-2016/kmp.html

版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！