字符串的几个问题

1.最长公共子序列
2.最长公共子串
3.最长回文串
4.最长回文序列
5.最长递增序列
6.最长先增后减序列
7.(最短)编辑距离
8.子串匹配问题
9.通配符问题

1.最长公共子序列（longest common subsequence， LCS）

动态规划解法

dp[i][j]表示字符串a的前i长度的子串a'，和b的前j个长度子串的b'的最长公共序列的长度

状态转移方程
$dp[i][j]= \begin{cases} dp[i-1][j-1]+1\space\space 当a[i-1] == b[i-1]时\\ max(dp[i-1][j],dp[i][j-1])\space\space 当a[i-1] != b[i-1]时 \end{cases}$

func LCS(a string, b string) int {
    dp := make([][]int, len(a)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        if i == 0 {
            continue
        }
        for j, _ := range dp[i] {
            if j == 0 {
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = dp[i-1][j]
                if dp[i][j-1] > dp[i][j] {
                    dp[i][j] = dp[i][j-1]
                }
            }
        }
    }

    return dp[len(a)][len(b)]
}

复杂度：
T = O(mn)
S = O(mn)

2.最长公共子串（longest common substring）

动态规划解法

记a[0:i]为a前i个长度的子串，b[0:j]为b前j个长度的子串
dp[i][j]表示a[0:i]和b[0:j]的以二者最后一个字符结尾的最长公共子串的长度
比如a是god，b是goods，dp[3][4]就是2（od的长度），dp[3][5]就是0

转移方程
$dp[i][j]= \begin{cases} dp[i-1][j-1]+1 \space\space 当a[i-1] == b[i-1]时\\ 0 \space\space 当a[i-1] != b[i-1]时 \end{cases}$

func LCSubstring(a string, b string) int {
    dp := make([][]int, len(a)+1)
    max := 0
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        if i == 0 {
            continue
        }
        for j, _ := range dp[i] {
            if j == 0 {
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = 0
            }
            if dp[i][j] > max {
                max = dp[i][j]
            }
        }
    }

    return max
}

暴力解

遍历a，依次与b的所有字符比较，如果a[i]==b[j]，再比较a中a[i]开头和b中b[j]开头的子串。

func LCSubstring(a string, b string) int {
    max := 0
    for i, _ := range a {
        for j, _ := range b {
            if a[i] != b[j] {
                continue
            }
            for k := i + 1; k < len(a); k++ {
                for l := j + 1; l < len(b); l++ {
                    if a[i:k+1] == b[j:l+1] && k+1-i > max {
                        max = k + 1 - i
                    }
                }
            }
        }
    }
    
    return max
}

最坏复杂度 $O(m^2*n^2)$

广义后缀数解

// 留坑

3.最长回文串

暴力解

遍历每个字符串
以当前字符a[i]为中心，向两边探测是否两侧字符是否相同
以当前字符a[i]、a[i+1]为中心，向两边探测是否两侧字符是否相同

func LPSubstring(a string) int {
    max := 0
    for i := 0; i < len(a); i++ {
        j := 1
        for ; i+j < len(a) && i-j >= 0 && a[i+j] == a[i-j]; j++ {
        }
        if 2*j-1 > max {
            max = 2*j - 1
        }

        if i < len(a)-1 && a[i] == a[i+1] {
            k := 1
            for ; i+1+k < len(a) && i-k >= 0 && a[i+1+k] == a[i-k]; k++ {
            }
            if 2*k > max {
                max = 2 * k
            }
        }
    }

    return max
}

时空复杂度
时间复杂度，最坏情况是整个字符串都由一个字符组成，每个字符都要向两侧探测到底。
T_worse = O(n^2)
S = O(1)

动态规划解

长度为1的子串，肯定是回文串
长度为2的子串，如果两字符相同，则是回文串
长度超过2的子串，如果首位字符相同，且首位之间也是回文串，则是回文串

设dp[i][j]表示起点为a[i]，终点为a[j]的子串是否为回文串
转移方程
$dp[i][j]= \begin{cases} 当j==i\space时，true \space\space \\ 当j==i+1时，\space\space 若a[i]==a[j], true。否则false \\ 当j>=i+2时，\space\space 若a[i]==a[j] 且 dp[i+1][j-1],true。否则false \\ \end{cases}$

当子串长度大于2时要依赖前面求解过的结果

试着推一下。假设有字符串abcdcf：
i=0,j=0，长度为1，true
i=0,j=1，长度为2，false
i=0,j=2，长度为3，需要判断a和c是否相同，如果相同，要依赖a[1][1]，但是a[1][1]不知道
所以i 递增，j 递增这个顺序推不行

换个方向：i 递增，j 递减
i=0,j=5，依赖a[1][4]，a[1][4]结果还没有出来，所以也不行

再换个方向：i 递减，j 递增
i=5,j=5，长度为1，无依赖
i=4,j=4，长度为1，无依赖
i=4,j=5，长度为2，无依赖
i=3,j=3，长度为1，无依赖
i=3,j=4，长度为2，无依赖
i=3,j=5，长度为3，依赖a[4][4]，a[4][4]已经出来了，a[3][5]可以推出

所以i 递减，j 递增这个方向推是可行的

微信图片_20220929134821.jpg

func LPSubstring(a string) int {
    dp := make([][]bool, len(a))
    max := 0
    for i := len(dp) - 1; i >= 0; i-- {
        dp[i] = make([]bool, len(a))
        for j := i; j < len(dp[i]); j++ {
            // 长度为1的子串肯定是回文串
            if j == i {
                dp[i][j] = true
                continue
            }
            // 长度为2的子串，俩字符相同即为回文串
            if j == i+1 {
                dp[i][j] = a[i] == a[j]
                continue
            }
            // 长度超过2的子串，俩字符相同且二者之间满足回文，则为回文串
            dp[i][j] = a[i] == a[j] && dp[i+1][j-1]
            if dp[i][j] && j-i+1 > max {
                max = j - i + 1
            }
        }
    }

    return max
}

复杂度
T(n) = O(n^2)
S(n) = O(n^2)

原串倒序+求解最长公共子串

将原来的字符串倒序，再求倒序串和原串的最长公共子串。如原串abadcf，倒序成fcdaba，求二者的最长公共子串。

马拉车算法(Manacher Algorithm)

该算法也是动态规划。
先假设存在的所有回文子串的长度都是奇数，所以对称中心是一个元素。
dp[i]表示以a[i]为对称中心的最长回文串的长度
用c、r分别表示目前发现的右边界最靠右的回文串的对称中心的位置，右边界的位置
初始c=0, r = 0
遍历原串，当前位置i一定满足i>=c，如果i<r，说明i处在一个对称的子串中

19f420a79ca4d4a9aaaac0516341cee.jpg

i关于c的对称点为i'，以i'为中心的最长回文串的左边界 Li'
如果Li' > r'，dp[i] = dp[i']
如果Li' <= r'，则说明dp[i]至少 >=r，然后以i为中心，r-i+1为起点距离向两边探测，如果发现在i串的右边界r之外，则更新c和r。
这样利用对称性就避免了从距离1开始向两侧探测。

如果i=r，没有捷径可走了，只能以i为中心点向外探测，探测完成后更新c和r
如果i>r，只能以i为中心点向外探测，探测完成后更新c和r

预处理原串，插入n+1个分割字符，将abadcf处理成_a_b_a_d_c_f_
现在所有的回文串长度都是奇数了，如a，_a_

func Manacher(a string) int {
    b := "_"
    for _, n := range a {
        b += string(n) + "_"
    }

    c := 0
    r := 0
    max := 0

    dp := make([]int, len(b))
    for i, _ := range dp {
        if i < r {
            i2 := 2*c - i // i的对称点
            if i+(dp[i2]-1)/2 < r {
                dp[i] = dp[i2]
            } else {
                j := r - i + 1
                for ; i+j < len(b) && i-j >= 0 && b[i+j] == b[i-j]; j++ {
                }

                if i+j-1 > r {
                    r = i + j - 1
                    c = i
                }

                dp[i] = 2*j - 1
                if dp[i] > max {
                    max = dp[i]
                }
            }
            continue
        }
        j := 1
        for ; i+j < len(b) && i-j >= 0 && b[i+j] == b[i-j]; j++ {
        }
        if i+j-1 > r {
            r = i + j - 1
            c = i
        }

        dp[i] = 2*j - 1
        if dp[i] > max {
            max = dp[i]
        }
    }

    return (max - 1) / 2
}

复杂度
T(n) = O(2n) = O(n) // 确定每个dp[i]需要O(n)，r从0增长到n-1也需要O(n)
S(n) = O(n)

4.最长回文序列

暴力解

有 $2^n$ 个子序列，检测其是否回文为序列，然后记录下最长的，所以暴力解基本不行。

原串倒序+求解原串和倒序串的最长公共子序列

动态规划解

设dp[i][j]表示子串以i为起点，j为终点的子串的最长回文序列。
转移方程：
$dp[i][j]= \begin{cases} dp[i+1][j-1]+2 \space\space 当a[i]==a[j]\space时\\ max(dp[i][j-1], dp[i+1][j])，\space\space 当a[i]!=a[j]\space时 \\ \end{cases}$
dp[i+1][j-1]表示的是i~j之间的子串的最优值，也就是去掉头尾i、j。应该注意判断子串的有效性，如i==j时，[i+1][j-1]这样的子串是不存在的。所以细化一下状态方程可以写成这样：
$dp[i][j]= \begin{cases} j=i时，1\\ j=i+1时， \begin{cases} 若a[i]=a[j]，则为2\\ 0 \end{cases} \\ j>= i+2时， \begin{cases} 若a[i]=a[j]，则为dp[i+1][j-1]+2\\ max(dp[i][j-1], dp[i+1][j]) \end{cases} \end{cases}$

同样需要i逆推，j正推

func LPS(a string) int {
    dp := make([][]int, len(a))
    for i := len(dp) - 1; i >= 0; i-- {
        dp[i] = make([]int, len(a))
        for j := i; j < len(a); j++ {
            if j == i {
                dp[i][j] = 1
                continue
            }
            if j == i+1 {
                if a[i] == a[j] {
                    dp[i][j] = 2
                } else {
                    dp[i][j] = 0
                }
                continue
            }
            if a[i] == a[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                max := dp[i][j-1]
                if dp[i+1][j] > max {
                    max = dp[i+1][j]
                }
                dp[i][j] = max
            }
        }
    }

    return dp[0][len(a)-1]
}

复杂度
T(n) = O(n^2)
S(n) = O(n^2)

5.最长递增序列

动态规划解

设dp[i]表示以i结尾的递增子序列的长度。
求取dp[i]:

首先dp[i]肯定至少为1
遍历0~i-1的元素，如果其中一个元素a[j]的取值小于a[i]，那a[j]+1就是a[j]的一个可能的取值，求出这些可能中的最大值即可

转移方程：
$dp[i] = max(dp[j]+1)，0 <= j < i，并且a[j] < a[i]$

func LongestIncreaseSequence(arr []int) int {
    dp := make([]int, len(arr))
    dp[0] = 1
    for i := 1; i < len(arr); i++ {
        dp[i] = dp[i-1]
        for j := 0; j < i; j++ {
            if arr[j] < arr[i] && dp[j]+1 > dp[i] {
                dp[i] = dp[j] + 1
            }
        }
    }

    return dp[len(arr)-1]
}

复杂度
T(n) = O(n^2)
S(n) = O(n)

二分查找

比如输入序列为arr := []int{1,5,2,3,9}
弄一个辅助数组a，初始值是输入序列的第一项
然后从index=1开始遍历arr，当前值为v， a的最后一项记作a.tail

如果v>a.tail，则将v添加到a后面，成为a的最后一项
如果v<=a.tail，则利用二分查找定位到a中第一个大于v的元素k，用v替换k

最终a的长度就是最长序列的长度。这很好理解，a就是被最长序列拓宽的。

func LongestIncreaseSequence(arr []int) int {
    b := []int{arr[0]}

    for i := 1; i < len(arr); i++ {
        if arr[i] > b[len(b)-1] {
            b = append(b, arr[i])
        } else if arr[i] < b[len(b)-1] {
            k := binarySearch(b, arr[i])
            b[k] = arr[i]
        }
    }
    return len(b)
}

func binarySearch(b []int, v int) int {
    // 找出切片b中，第一个大于v的元素的位置
    left := 0
    right := len(b) - 1

    for right > left {
        mid := (left + right) / 2
        if b[mid] < v {
            left = mid + 1
        } else {
            right = mid
        }
    }

    if b[left] < v {
        return -1 // 没有找到
    }

    return left
}

复杂度
T(n) = O(nlogn)
S(n) = O(n)

6.最长先增后减序列

只要这个序列满足先递增，后递减就行，不要求中心点两边的数量一样多

先求递增+再求递减

先求出以i结尾的递增序列长度，在求出以i为起点的递减序列长度，两个长度之和-1，就是以i为最高点的序列的先增后减序列的长度。

牛客网-合唱队问题

7.(最短)编辑距离

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。
例如：
字符串A: abcdefg
字符串B: abcdef
通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
要求：
给定任意两个字符串，写出一个算法计算它们的编辑距离

动态规划解

设有字符串A、B
A[0:i]表示A的 [0,i) 这个区间组成的字符串
设dp[i][j]表示A[0:i]和字符串B[0:j](最短)编辑距离，如dp[1][1]表示a的首字符编辑成b的首字符

当两个子串的末字符相同时，dp[i][j] = dp[i-1][j-1]

可以用反正法证明一下：
假设dp[i][j]不等于dp[i-1][j-1]
也就是A[0:i]和B[0:j]存在比dp[i-1][j-1]更优的解K，K<dp[i-1][j-1]
也就是经过K次编辑A[0:i]和B[0:j]相同，此时A[0:i-1]和B[0:j-1]也相同
也就是A[0:i-1]和B[0:j-1]也存在更优解K<dp[i-1][j-1]
与题设dp[i-1][j-1]为A[0:i-1]和B[0:j-1]的最优解矛盾

当两个子串的末字符不相同时

微信图片_20220930174240.jpg

A→B有几种可能：
A'→B'，然后a→b
A'+a → B'，然后后面补充一个b
A'→B'+b，然后删除末尾的a
此时最优值在三种情况中取最小

func MinEditDistance(a string, b string) int {
    dp := make([][]int, len(a)+1)
    for i, _ := range dp {
        dp[i] = make([]int, len(b)+1)
        for j, _ := range dp[i] {
            if i == 0 {
                dp[i][j] = j
                continue
            }
            if j == 0 {
                dp[i][j] = i
                continue
            }
            if a[i-1] == b[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                min := dp[i-1][j-1] + 1
                if dp[i][j-1]+1 < min {
                    min = dp[i][j-1] + 1
                }
                if dp[i-1][j]+1 < min {
                    min = dp[i-1][j] + 1
                }
                dp[i][j] = min
            }
        }
    }
    return dp[len(a)][len(b)]

}

复杂度
T(n) = O(m*n)
S(n) = O(m*n)

牛客网-计算编辑距离

8.子串匹配问题

在主串中寻找子串，如在主串s = "abcde" 中寻找子串sub = "ab"，如果找到，返回首次出现位置，如果不存在，返回-1

暴力解：

指针i遍历主串，j遍历子串，当失配时，从i+1开始令j=0重新比较

func SearchSubstring(s string, sub string) int {
    i := 0
    j := 0
    for i < len(s) && j < len(sub) {
        if s[i] == sub[j] {
            i++
            j++
        } else {
            i = i + 1
            j = 0
        }
    }

    if j == len(sub) {
        return i - len(sub)
    }

    return -1
}

最坏复杂度，每次都要比较到子串的最后一个字符才发现不匹配，如aaaaaaaaab，aaab。
T_worse = O((n-m+1)*m) = O((n-m)*m)

KMP算法（Knuth-Morris-Pratt Algorithm)

再看一下暴力破解过程，假如主串指针走到i、子串指针走到j时，发生了失配，然后就从i的下一个位置（即i+1）开始，把子串从头到尾重新比较。

主串： | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |...
子串： | a | b | c | a | b | ?|...
假设当 j = 5 时出现失配，说明j前面的部分是和主串吻合的
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： | a | b | c | a | b | ? |...
按照暴力算法是从主串当前起始点的下一位开始从头比较
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： ----| a | b | c | a | b | ? |...

上帝视角可以发现，i+1这个位置根本不用比较，因为此时的第一位b和a就对不上，同样i+2这个位置也不用，因为c和a也是第一位就对不上。只有走到i+3，才有可能匹配。
主串： | a | b | c | a | b | ? | ? | ? | ? | ? | ? |...
子串： ------------| a | b | c | a | b | ? |...

这就是kmp的特点，主串指针i不用回头，将子串指针j回头到某个位置即可。（此时前两位a=a，b=b是确定的，所以j也不用直接回到0。）

当j在某个位置发生失配，需要知道j的下一跳应该跳到哪个位置继续，假设这个信息存在一个叫next的表中，并且我们已经得到了next表。此时程序应该这么写：

func KMP(a string, b string) (allMatches []int) {
    i := 0
    j := 0

    next := buildNext(b)
    for i < len(a) {
        if j == len(b) {
            allMatches = append(allMatches, i-len(b))
            j = 0
        }
        if a[i] == b[j] {
            i++
            j++
        } else {
            if j == 0 { // 如果在子串首字符就失配，应将主串指针右移，子串指针不变
                i++
            } else {
                j = next[j]
            }
        }

    }

    return
}

重点是如何构造next表

主串： | a | b | - | a | b | ? |...
子串： | a | b | - | a | b | ? |...

主串： | a | b | c | - | - | - |a |b| c| ? |...
子串： | a|b| c| - | - | - | a | b | c | ? |...

主串： | a | b | c | - | - | - | - | - |a |b| c| ? |...
子串： | a|b| c| - | - | - | - | - | a | b | c | ? |...

只要把前面标红的一截和后面标红的一截对齐，这段标红的区域叫做最长公共前后缀，j从红色区域的下一个字符开始比较。

字符串s的前缀的定义是：起点为0，终点在最后一个字符前的子串。比如abc的前缀有两个a、ab，类似地，后缀有c、bc。一个前缀和一个后缀相同，这就是一个公共前后缀。比如abcab的最长公共前后缀是ab。

next[j]是在j失配时的下一跳位置，也是sub[0:j]的最长公共前后缀长度。比如由sub="abcde"构建的next表，next[2]表示在c发生失配时的下一跳，也表示ab的最长公共前后缀长度。所以有些编码中也把next table叫prefix table。

假如sub="aaacd"，要求解的内容是：
next[1] 表j=1失配时的下一跳，也是a的最长公共前后缀，0
next[2] 表j=2失配时的下一跳，也是aa的最长公共前后缀，1
next[3] 表j=3失配时的下一跳，也是aaa的最长公共前后缀，2
next[4] 表j=4失配时的下一跳，也是aaac的最长公共前后缀，0

构造next表不需要暴力解，可以递推出来。
首先next[1]肯定是0，当next[k]已经求解出来后，直接比较最长公共前后缀的下一字符是否相同，如果相同，那就可以构成一个更长的公共前后缀。所以next[k+1] = next[k]+1。就像下面的两个问号代表的内容如果相同，就可以形成长度为3公共前后缀。
| a | b | ? | ... | a | b | ? |...

如果不同的话，说明无法构成一个更长的公共前后缀，就要尝试是否能构成更短的。

如下，因为e和b不同，所以无法形成长度为5的公共前后缀

| a | b | c | a | e | ... | a | b | c | a | b |
|-----(1)-----|-------|-----(2)-----|

于是可以在(2)寻找一个后缀，使得它等于(1)一个前缀，然后验证此时是否能为末尾的b找到相同的元素。因为(1)和(2)是相同的，所以相当于在(1)中找最大公共前后缀，直接读取next[4]就知道了，此时next[4]值为1，所以问题又回到了上面的比较公共前后缀的下一字符是否相同。

如果相同，最长公共前后缀+1
如果不同，继续在后缀中找更小的后缀，比较下一字符是否相同...
直到末字符匹配上了或者找到的next[x]是0

func buildNext(sub string) []int {
    next := make([]int, len(sub))
    for i := 2; i < len(sub); i++ {
        l := next[i-1]
        for l != 0 && sub[l] != sub[i-1] {
            l = next[l]
        }

        if sub[l] == sub[i-1] {
            next[i] = l + 1
        } else {
            next[i] = 0
        }
    }

    return next
}

构造next表可以看成在sub中，从i=1开始从搜索自己的前缀

func buildNext2(sub string) []int {
    next := make([]int, len(sub))
    i := 1
    j := 0

    for i < len(sub)-1 {
        if sub[i] == sub[j] {
            next[i+1] = j + 1
            i++
            j++
            continue
        }
        if j == 0 {
            next[i+1] = 0
            i++
        } else {
            j = next[j]
        }
    }

    fmt.Println(next)
    return next
}

9.字符串通配符

定义：
?匹配一个字符
*匹配任意多个字符，可以为0个，同样
能被*和?匹配的字符仅由英文字母和数字0到9组成
给出一个字符串s，一个通配符表达式p，请判断这个字符串是否完全匹配这个通配符。
比如abb匹配a*b，abc不匹配a*b。

动态规划解

dp[i][j]表示s[0:i]是否匹配p[0:j]，0<= i <= len(s)，0<= j <= len(p)

递推关系：
如果p[j-1]是个普通字符：

s[i-1]和p[j-1]相同，并且dp[i-1][j-1]为true，则dp[i][j]为true
否则false

如果p[j-1]是"?"

s[i-1]为字母或数字，并且dp[i-1][j-1]为true，则dp[i][j]为true
否则false

如果p[j-1]是"*"，有两种情况可以判定dp[i][j]为true，其余则为false

当dp[i-1][j]为true时，并且最后这个字符是数字或字母。
(也就是因为ab*可以匹配abc，所以它也能匹配abcd，abcde...)
如果dp[i][j-1]为true，此时"*"可以解读为空字符，所以为true，如ab和ab*

func IsMatch(p string, s string) bool {
    dp := make([][]bool, len(s)+1)
    // dp[i][j]表示s的前i个字符和模式p的前j个字符是否匹配
    for i, _ := range dp {
        dp[i] = make([]bool, len(p)+1)
        for j, _ := range dp[i] {
            if i == 0 {
                if j == 0 {
                    dp[i][j] = true
                } else {
                    if p[j-1] == '*' {
                        dp[i][j] = dp[i][j-1]
                    } else {
                        dp[i][j] = false
                    }
                }
                continue
            }

            if j == 0 {
                dp[i][j] = false
                continue
            }

            pj := p[j-1]
            si := s[i-1]

            if pj == '?' {
                dp[i][j] = dp[i-1][j-1] && (isLetter(si) || isNumber(si))
                continue
            }

            if pj == '*' {
                dp[i][j] = (dp[i-1][j] && (isLetter(si) || isNumber(si))) || dp[i][j-1]
                continue
            }

            dp[i][j] = dp[i-1][j-1] && lower(pj) == lower(si)
        }
    }

    return dp[len(s)][len(p)]
}

func isLetter(n byte) bool {
    return (n >= 'a' && n <= 'z') || (n >= 'A' && n <= 'Z')
}

func isNumber(n byte) bool {
    return n >= '0' && n <= '9'
}

func lower(n byte) string {
    return strings.ToLower(string(n))
}

最后编辑于：2022.11.01 00:43:49

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,530评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 86,403评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,120评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,770评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,758评论 5赞 367
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,649评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,021评论 3赞 398
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,675评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,931评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,659评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,751评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,410评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,004评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,969评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,203评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,042评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,493评论 2赞 343

字符串的几个问题

1.最长公共子序列（longest common subsequence， LCS）

动态规划解法

2.最长公共子串（longest common substring）

动态规划解法

暴力解

广义后缀数解

3.最长回文串

暴力解

动态规划解

原串倒序+求解最长公共子串

马拉车算法(Manacher Algorithm)

4.最长回文序列

暴力解

原串倒序+求解原串和倒序串的最长公共子序列

动态规划解

5.最长递增序列

动态规划解

二分查找

6.最长先增后减序列

先求递增+再求递减

7.(最短)编辑距离

动态规划解

8.子串匹配问题

暴力解：

KMP算法（Knuth-Morris-Pratt Algorithm)

9.字符串通配符

动态规划解

推荐阅读更多精彩内容