扩展KMP算法 » NoAlGo博客
扩展KMP算法：给定一个较长的主字符串S和一个较短的模式串T，用m、n分别表示S和T的长度（即m=|S|，n=|T|），定义extend[i]=S[i..n]与T的最长公共前缀的长度，求extend[i]。
为什么说这是KMP算法的扩展呢？显然，如果在S的某个位置x有extend[x]==n，则可知在S中可以找到T，并且首位置是x，这正是KMP算法要解决的问题。而且，扩展KMP算法能找到S中所有T的匹配，更一般地，可以知道S中以每个字符开始的后缀与T的最大的匹配长度（最长公共前缀长度）。
Read full article from 扩展KMP算法 » NoAlGo博客
扩展KMP算法：给定一个较长的主字符串S和一个较短的模式串T，用m、n分别表示S和T的长度（即m=|S|，n=|T|），定义extend[i]=S[i..n]与T的最长公共前缀的长度，求extend[i]。
为什么说这是KMP算法的扩展呢？显然，如果在S的某个位置x有extend[x]==n，则可知在S中可以找到T，并且首位置是x，这正是KMP算法要解决的问题。而且，扩展KMP算法能找到S中所有T的匹配，更一般地，可以知道S中以每个字符开始的后缀与T的最大的匹配长度（最长公共前缀长度）。
Read full article from 扩展KMP算法 » NoAlGo博客
