字符串算法

2018-02-11

字符串

字符串循环左移

例如‘abcdef’，左移两个字符串，变成‘cdefab’。

str='abcdef'
k=100   # 任意指定
x=k%len(str)
str1=str[0:x]
str2=str[x:]
str3=str2+str1

如果有对空间的限制，这道题就需要通过逆序的方法了。过程如下：
upload successful

字符串全排列

S=[0….N-1]，枚举S的全排列

str='1234'
def swap(a,i,foo):
    tmp=a[0:i]+a[foo]
    if i!=len(a):
        tmp+=a[i+1:]
    str=tmp[0:foo]+a[i]
    if foo!=len(a):
        str+=tmp[foo+1:]
    return str

def Permutation(str,foo,to):
    if foo==to:
        for i in range(0,to):
            print(str[i],end='')
        print()
        return
    for i in range(foo,to):
        x = swap(str,i,foo)
        Permutation(x,foo+1,to)
Permutation(str,0,4)

KMP

给定文本串text和模式串pattern，从文本串中找出模式串第一次出现的位置。
例如甲：abbaabbaaba，乙：abbaaba。查找乙在甲什么位置。
假定文本串长度是N，模式串长度为M，普通模式匹配算法（BF）时间复杂度：O(M*N)，空间复杂度O(1)。而KMP算法可以用闲心时间算法求解匹配字符串问题的方法，时间复杂度：O(M+N)，空间复杂度O(M)。
BF方法从两个字符串头开始，若遇到不匹配的字符，模式串回溯到开始位置，文本串回溯到头结点+1。然后继续匹配，如果模式串中字符两两不相等，那么这样会造成很多没必要的匹配过程。

str1 = 'abbaabbaaba'
str2 = 'abbaaba'
def BF(str1,str2):
    i=0
    while i <len(str1):
        j=0
        while j <len(str2) and str1[i]==str2[j]:
            i+=1
            j+=1
        if j==len(str2):
            print('success')
            return i-len(str2)
        i=i-j+1
    return -1

paste image
KMP方法的思路是，尽量减少指针回溯，当出现不匹配字符时，前六个字符已经知道了，如果模式串不回溯到开始位置，而是移动到后面的匹配的位置，这样就提高了效率。
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。
paste image

paste image
已知空格与D不匹配时，可以根据公式：

1	移动位数 = 已匹配的字符数 - 对应的部分匹配值

计算得出文本串最后一个字符与模式串部分匹配值为2，已匹配的字符为6个，所以模式串要后移6-2=4位。
paste image
此时再判断C与空格不匹配，这时部分匹配值为0，移动位移数为2，也就从头匹配了。
然后继续比较，直到完全匹配，或者文本串结尾。

然后就是部分匹配值的算法，首先要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。”部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

“A”的前缀和后缀都为空集，共有元素的长度为0；
“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动 4 位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

str1 = 'abbaabbaaba'
str2 = 'abbaaba'

#返回索引
def next_index(str,i):
    j=0
    while str[j]==str[i-j]:
        j+=1
    return j

def KMP(str1,str2):
    i,j=0,0
    while i <len(str1):
        j=next_index(str2,j)
        while j <len(str2) and str1[i]==str2[j]:
            i+=1
            j+=1
        if j==len(str2):
            print('success')
            return i-len(str2)
    return -1
print(KMP(str1,str2))

BF算法循环了14次，KMP循环11次，不算计算next_index的次数的话，减少了迭代次数。如果第一字符跟后面都不同，则KMP算法next总返回开始。

Manacher算法

最长回文子串问题：给定一个字符串，求它的最长回文子串长度。
对于最长回文子串问题，最简单粗暴的办法是：找到字符串的所有子串，遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定，因此对于一个长度为n的字符串，共有n^2个子串。这些子串的平均长度大约是n/2，因此这个解法的时间复杂度是O(n^3)。
希望能提高算法的效率。Manacher正是针对这些问题改进算法。

解决长度奇偶性带来的对称轴位置问题
Manacher算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的。以插入#号为例：
1
2
aba ———> #a#b#a#
abba ———> #a#b#b#a#

插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响，原来是回文的串，插完之后还是回文的，原来不是回文的，依然不会是回文。

解决重复访问的问题
我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher定义了一个回文半径数组RL，用RL[i]表示以第i个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理，因此这里定义RL[i]为第i个字符为对称轴的回文串的最右一个字符与字符i的距离。对于上面插入分隔符之后的两个串，可以得到RL数组：
1
2
3
4
5
6
7
8
char: # a # b # a #
RL : 1 2 1 4 1 2 1
RL-1: 0 1 0 3 0 1 0
i : 0 1 2 3 4 5 6
char: # a # b # b # a #
RL : 1 2 1 2 5 2 1 2 1
RL-1: 0 1 0 1 4 1 0 1 0
i : 0 1 2 3 4 5 6 7 8

上面我们还求了一下RL[i]-1。通过观察可以发现，RL[i]-1的值，正是在原本那个没有插入过分隔符的串中，以位置i为对称轴的最长回文串的长度。那么只要我们求出了RL数组，就能得到最长回文子串的长度。
于是问题变成了，怎样高效地求的RL数组。基本思路是利用回文串的对称性，扩展回文串。
我们再引入一个辅助变量MaxRight，表示当前访问到的所有回文子串，所能触及的最右一个字符的位置。另外还要记录下MaxRight对应的回文串的对称轴所在的位置，记为pos，它们的位置关系如下。
paste image
我们从左往右地访问字符串来求RL，假设当前访问到的位置为i，即要求RL[i]，在对应上图，i必然是在po右边的(obviously)。但我们更关注的是，i是在MaxRight的左边还是右边。我们分情况来讨论。
1）当i在MaxRight的左边
情况1)可以用下图来刻画：
paste image
我们知道，图中两个红色块之间（包括红色块）的串是回文的；并且以i为对称轴的回文串，是与红色块间的回文串有所重叠的。我们找到i关于pos的对称位置j，这个j对应的RL[j]我们是已经算过的。根据回文串的对称性，以i为对称轴的回文串和以j为对称轴的回文串，有一部分是相同的。这里又有两种细分的情况。
以j为对称轴的回文串比较短，短到像下图这样。
paste image
这时我们知道RL[i]至少不会小于RL[j]，并且已经知道了部分的以i为中心的回文串，于是可以令RL[i]=RL[j]。但是以i为对称轴的回文串可能实际上更长，因此我们试着以i为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。
以j为对称轴的回文串很长，这么长：
paste image
这时，我们只能确定，两条蓝线之间的部分（即不超过MaxRight的部分）是回文的，于是从这个长度开始，尝试以i为中心向左右两边扩展，，直到左右两边字符不同，或者到达边界。
不论以上哪种情况，之后都要尝试更新MaxRight和pos，因为有可能得到更大的MaxRight。
具体操作如下：

1
2
3

step 1: 令RL[i]=min(RL[2*pos-i], MaxRight-i)
step 2: 以i为中心扩展回文串，直到左右两边字符不同，或者到达边界。
step 3: 更新MaxRight和pos

2）当i在MaxRight的右边
paste image
遇到这种情况，说明以i为对称轴的回文串还没有任何一个部分被访问过，于是只能从i的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新MaxRight和pos。

def manacher(s):
    #预处理
    s1='#'+'#'.join(s)+'#'
    p=[0]*len(s1) # 回文半径列表
    mx=0 # 当前索引回文串最远的索引值
    id=0 # 当前指向探测最远的索引
    for i in range(len(p)):
        if mx>i:
            p[i]=min(p[2*id-i],mx-i) # 两种情况，取最小的哪一种，利用已知条件确定p[i]的值
        else:
            p[i]=1  # 无法从已知条件找到，先赋值为1
        while (i+p[i])<len(s1) and s1[i+p[i]]==s1[i-p[i]] :
            p[i]+=1  # 更新p[i]，向外探索回文的范围
        if mx<i+p[i]: #更新mx和id
            mx=i+p[i]
            id=i
    return max(p)-1

BM算法

KMP在实际中并不是很快，BM算法相比较效率会更高一些，而且算法也更巧妙。
具体方法：坏字符原则、好后缀。