hiho一下第227周《Longest Subsequence》题目分析

9
0

《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| )的。

write answer 切换为英文 切换为中文


转发分享