字符串预处理

当我们有大量的时间用于在 s中找到下一个匹配字符时

我们可以通过预处理，得到：对于 s 的每一个位置，从该位置开始往后每一个字符第一次出现的位置。

我们可以使用动态规划的方法实现预处理，令 f[i][j]表示字符串 s中从位置 i开始往后字符 j 第一次出现的位置。在进行状态转移时，如果 s中位置 i的字符就是 j，那么 f[i][j]==i，否则 f[i][j]=f[i+1][j]；因此我们要倒过来进行动态规划，从后往前枚举 i。

这样我们可以写出状态转移方程：

这样，我们可以利用 f 数组，每次 O(1) 地跳转到下一个位置，直到位置变为 m 或 t 中的每一个字符都匹配成功。

代码参考：（leetcode 524）给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

func findLongestWord(s string, dictionary []string) (ans string) {
    m := len(s)
    f := make([][26]int, m+1)
    for i := range f[m] {
        f[m][i] = m//表示之后再也没有该字符了
    }
    for i := m - 1; i >= 0; i-- {
        f[i] = f[i+1]//整组赋值思路很棒！
        f[i][s[i]-'a'] = i
    }
outer:
    for _, t := range dictionary {
        j := 0
        for _, ch := range t {
            if f[j][ch-'a'] == m {
                continue outer//在标定位继续的思路
            }
            j = f[j][ch-'a'] + 1
        }
        if len(t) > len(ans) || len(t) == len(ans) && t < ans {
            ans = t
        }
    }
    return
}