Skip to content

Latest commit

 

History

History
293 lines (229 loc) · 8.22 KB

2018-04-10-字符串中的子串问题.md

File metadata and controls

293 lines (229 loc) · 8.22 KB
layout title date categories
post
字符串中的子串问题
2018-04-11 20:00:05 +0800
算法

问题描述

在阅读《编程珠玑》第二版字符串一章中提到了一个解决寻找最长子串的问题的方案，之前还没见识过这方案，今天阅读后觉得有必要 mark down。

如何寻找字符串中重复出现的最长子串？

算法介绍

注意：以下代码使用 Go 实现。简单起见，假设所有输入都是 ASCII 编码的字符，因为 Go 使用 UTF-8 编码，解码 utf-8 操作需要额外操作，而这里以介绍算法为主。

Go 中采用了类似 Java 的字符串池化的概念，取子串的消耗非常低，因为底层复用了父字符串，所以在算法实现中使用了大量的取字符串的子串操作。

先定义一个用于计算两个字符串相同前缀的长度的函数：

func commonLen(i, j int, s string) (cnt int) {
    if i > j {
        i, j = j, i
    }
    for j < len(s) && s[j] == s[i] {
        cnt++
        i++
        j++
    }
    return cnt
}

嵌套循环

最简单的解决方案是使用两个循环进行比较：

func TwoCircle(source string) string {
    maxLen := 0
    maxStart := 0
    for i := 0; i < len(source)-1; i++ {
        for j := i + 1; j < len(source); j++ {
            if r := commonLen(i, j, source); r > maxLen {
                maxLen = r
                maxStart = i
            }
        }
    }
    return source[maxStart: maxStart+maxLen]
}
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

后缀数组

Step 1 从第 0 个位置开始，每次切割切割字符串中头部，比如 banana，定义指针数组 char *a[6]：

a[0] = "banana"
a[1] = "anana"
a[2] = "nana"
a[3] = "ana"
a[4] = "na"
a[5] = "a"

规律：每个字符串拥有相同的后缀

step 2 对 a 指针数组进行排序，其比较规则是根据指针指向数组的大小，结果为：

a[0] = "a"
a[1] = "ana"
a[2] = "anana"
a[3] = "banana"
a[4] = "na"
a[5] = "nana"

规律：具有相同前缀的字符串互相相邻

step 3 遍历数组 a 比较相邻元素，找出最长子串长度。上面的排序操作的目的就是为了让具有相同前缀的字符串相邻，这样进行比较操作时，只需要与相邻元素进行比较，而不需要从头到尾进行比较。

显而易见，最长子串是：ana

代码实现

func SuffixArray(source string) string {
    // 因为 Go 中指针不可运算，所以这里我们存储的是字符的起始位置
    sarr := make([]int, len(source))
    for i := 0; i < len(sarr); i++ {
        sarr[i] = i
    }
    ssa := StringSuffixArray{sarr:sarr, source:source}
    sort.Sort(&ssa)
    // 对排序后的子字符串，每个字符串与右边字符串进行比较，寻找字符串中重复出现的最长子串
    maxStart, maxLen := 0, 0
    for i := 0; i < len(sarr) - 1; i++ {
        if r := commonLen(sarr[i], sarr[i+1], source); r > maxLen {
            maxLen = r
            maxStart = sarr[i]
        }
    }
    return source[maxStart:maxStart+maxLen]
}

// 以下代码是为实现 sort.Interface 接口，使用 Go 自带的快速排序算法
type StringSuffixArray struct {
    sarr   []int
    source string
}

func (s *StringSuffixArray) Less(i, j int) bool {
    return strings.Compare(s.source[s.sarr[i]:], s.source[s.sarr[j]:]) < 0
}

func (s *StringSuffixArray) Swap(i, j int) {
    s.sarr[i], s.sarr[j] = s.sarr[j], s.sarr[i]
}

func (s *StringSuffixArray) Len() int {
    return len(s.sarr)
}
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)

基于后缀数组实现查找字符串中重复出现的最长子串算法，时间主要花费在对子串进行排序。

衍生问题

至少重复 M 次的串

已经找到了“查找重复出现的最长子串”（问题一）的算法，那请思考如何实现“查找重复出现至少 M 次的最长子串”（问题二）？

可以尝试着寻找问题一与问题二有哪些共通之处：

  1. 重复出现
  2. 子串

在阅读下面之前希望读者先花几分钟思考一样如何使用后缀数组实现。

解决算法

对后缀数组排序后得到的子串的特点是：

  1. 每个字符串具有相同的后缀
  2. 具有相同、相似前缀的字符串相邻

这里假设一个字符串："bananana"，寻找重复出现至少 3 次的最长子串。

step 1 从头到为取后缀子串：

a[0] = "bananana"
a[1] = "ananana"
a[2] = "nanana"
a[3] = "anana"
a[4] = "nana"
a[5] = "ana"
a[6] = "na"
a[7] = "a"

step 2 对后缀数组进行排序，得到结果：

a[0] = "a"
a[1] = "ana"
a[2] = "anana"
a[3] = "ananana"
a[4] = "bananana"
a[5] = "na"
a[6] = "nana"
a[7] = "nanana"

比较子串相同部分的长度主要是比较其前缀，和相邻元素进行比较是寻找重复出现至少 2 次的子串（这个结论很重要）。

那么要寻找至少重复出现 M 次的子串，则只需要 a[i] 与 a[i+M-1] 进行前缀对比，找出相同前缀的长度。

为什么？

因为如果 a[i] 与 a[i+M-1] 具有相同的前缀 prefix，那么可以证明 a[i] 与 a[i+1]、a[i+2]....a[i+M-1] 都具有 prefix 前缀，a[i]...a[i+M-1] 共有 M 个子串，所以能够保证 prefix 至少重复出现了 M 次。（可以借鉴 "bananana" 的排序后的子串）

代码实现

func SubStringDuplicateMTimes(source string, M int) string {
    if M <= 1 {
        return source
    }
    sarr := make([]int, len(source))
    for i := 0; i < len(sarr); i++ {
        sarr[i] = i
    }
    ssa := StringSuffixArray{sarr:sarr, source:source}
    sort.Sort(&ssa)
    maxStart, maxLen := 0, 0
    // 从后往前遍历
    for i := len(sarr) - 1; i - M + 1 >= 0; i-- {
        if r := commonLen(sarr[i], sarr[i-M+1], source); r > maxLen {
            maxLen = r
            maxStart = sarr[i]
        }
    }
    return source[maxStart:maxStart+maxLen]
}

两个字符串中最长公共子串

这是面试腾讯实习时一道面试题。

后缀数组是针对一个字符串的，如果题目给出了两个或者多个字符串应该怎么办呢？

将两个字符串拼接成一个字符串。

最后更新公共子串时只要保证不越界即可，具体代码如下：

func LongestCommonSubstring(s, t string) string {
    // merge to one string and use suffix array.
    m := s + t
    sl, ml := len(s), len(m)
    arr := make([]int, ml)
    for i := 0; i < ml; i++ {
        arr[i] = i
    }
    maxLen, start := 0, 0
    sort.Sort(&StringSuffixArray{arr, m})
    for x := 0; x < ml-1; x++ {
        ax := arr[x]
        for y := x + 1; y < ml; y++ {
            ay := arr[y]
            if ax > ay {
                ax, ay = ay, ax
            }
            if ax >= sl && ay < sl {
                continue
            }
            if v := commLen(ax, ay, m); v > maxLen {
                if ax+v > sl {
                    v = sl - ax
                }
                if v > maxLen {
                    maxLen, start = v, ax
                }
            }
        }
    }
    return s[start : start+maxLen]
}

字符串中最长回文串

设串 s：abccbaccdcpffpcdef，求字符串中最长回文串。答案是显然的 dcpffpcd。

回文串的特点：正序与逆序相等。

解决方案：

  1. 令 t 为 s 的反转（t = "fedcpffpcdccabccba"）
  2. 求 s 与 t 的最长公共子串
func longestPalindrome(s string) string {
    t := reverse(s)
    return LongestCommonSubstring(s, t)
}

// reverse string s
// note: only for ascii
func reverse(s string) string {
    t := []rune(s)
    for i, j := 0, len(s) - 1; i < j; i, j = i + 1, j - 1 {
        t[i], t[j] = t[j], t[i]
    }
    return string(t)
}

写在最后

《编程珠玑》中多次提到不要用几分钟思考算法，用几个小时去实现；而应该用一个小时去思考，几十分钟去实现。厉害的程序员总是很“懒”的，大部分时间都不在写代码，而是思考。