(1) "好后缀"的位置以最后一个字符为准。假定"ABCDEF"的"EF"是好后缀,则它的位置以"F"为准,即5(从0开始计算)。 (2) 如果"好后缀"在搜索词中只出现一次,则它的上一次出现位置为 -1。比如,"EF"在"ABCDEF"之中只出现一次,则它的上一次出现位置为-1(即未出现)。 (3) 如果"好后缀"有多个,则除了最长的那个"好后缀",其他"好后缀"的上一次出现位置必须在头部。比如,假定"BABCDAB"的"好后缀"是"DAB"、"AB"、"B",请问这时"好后缀"的上一次出现位置是什么?回答是,此时采用的好后缀是"B",它的上一次出现位置是头部,即第0位。这个规则也可以这样表达:如果最长的那个"好后缀"只出现一次,则可以把搜索词改写成如下形式进行位置计算"(DA)BABCDAB",即虚拟加入最前面的"DA"。
The Boyer-Moore string-search algorithm is an efficient string-searching algorithm that is the standard benchmark for practical string-search literature. The algorithm preprocesses the pattern string instead of the string being searched in. The BM algorithm uses information during preprocess and it can skip along the text in jumps of multiple characters rather than searching every single character in the text. Specifically speaking, the start of pattern string will be aligned with the start of text string at the beginning. Characters are then compared from the end of pattern string, moving backward. If a mismatch occurs, the alignment will be shifted forward according to the maximum value permitted by several rules. The comparisons will be performed again at the new alignment. A shift is calculated by applying two rules: the bad character rule and the good suffix rule. The bad character rule considers the character at which the comparision process failed. The next occurrence of that character to the left is found, and a shift which brings that occurrence with the mismatched occurrence is proposed. Whereas the good suffix rule considers the suffix that has been matched and a shift which brings the occerrence with the matched occurrence is proposed. The BM algorithm has worst-case running time of O(nm), and the best-case running time is O(n/m). Generally speaking, the algorithm run faster as the pattern length increases.
实现一个函数用来匹配包括’.’和’’的正则表达式。模式中的字符’.’表示任意一个字符,而’’表示它前面的字符可以出现任意次(包含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串
一个字符串的排列是否是另一个字符串的子串
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
两个字符串 A 和 B。 A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde',在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后,A 能变成B,那么返回True。