《Longest Subsequence》题目分析

一般我们判断字符串Wi是不是字符串S的子序列，复杂度是O(|S|)的：

我们从左向右从S里找到一个字符Wi[0]，再向右找第一个Wi[1]，再向右找第一个Wi[2]...，直到找到Wi最后一个字符或者S结束也没有找完Wi。

不过如果我们能先计算出来f[i][c]表示S[i]之后，第一个字符c的位置，那么上面的计算过程可以优化到O(|Wi|)：

因为一旦我们找到S[i]是第一个Wi[0]之后，再向右的第一个Wi[1]的位置就是f[i][Wi[1]]，再向右第一个Wi[2]的位置就是f[ f[i][Wi[1]] ][Wi[2]] ...

而f数组的计算可以通过从后向前扫描S，O(26 * |S|)计算出来。

有了f之后，再依次计算Wi是不是S的子序列，总复杂度是O( Σ|Wi| )的。