扩展KMP

Finding Palindromes(POJ-3376) 题面 A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, “dad”, “eye” and “racecar” are all palindromes, but “odd”, “see” and “orange” are not palindromes. Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes. ...

简介 给定长度为n的文本串S和长度为m的模式串T，定义extend[i]为S[i…n-1]与T[0…m-1]的最长公共前缀长度，求extend[i]。当extend[x]==m时，则可知文本串S中包含模式串T，并且首位置为x，而这正是KMP算法处理的模式匹配问题。相较于KMP算法，扩展KMP算法能找到文本串S中所有模式串T的匹配，更一般地，可以知道文本串S中以每个字符开始的后缀与模式串T的最长公共前缀长度，时间复杂度O(n+m)。 ...