python - 使用预计算针对特定用例优化 Python 算法

Question

我正在尝试解决此处提到的问题的特定变体:

给定一个字符串 s 和一个字符串 t，检查 s 是否是 t 的子序列。

我写了一个算法，可以很好地解决上述问题:

def isSubsequence(s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        i = 0

        for x in t:
            if i<len(s) and x==s[i]:
                i = i + 1

        return i==len(s)

现在有一个特定的用例:

如果有很多传入的 S，例如 S1、S2、...、Sk，其中 k >= 10 亿，并且您想一个一个地检查 T 是否有其子序列。

有个提示:

/**
 * If we check each sk in this way, then it would be O(kn) time where k is the number of s and t is the length of t. 
 * This is inefficient. 
 * Since there is a lot of s, it would be reasonable to preprocess t to generate something that is easy to search for if a character of s is in t. 
 * Sounds like a HashMap, which is super suitable for search for existing stuff. 
 */

但是这个逻辑似乎把上面算法的逻辑颠倒过来了，如果遍历 s 并且使用 hashmap 在 t 中搜索字符，它不会总是正确的，因为 t 的 hashmap 对于该字符只有 1 个索引并且不能保证订单将被保留。

所以，我对如何针对上述用例优化算法感到困惑？

感谢您的帮助。

Answer 1

对于小于len(t)的每个i，以及出现在t中的每个字符c，从 (i,c)->j 进行映射，其中 j 是第一个索引 >= i ，即 c 发生。

然后您可以遍历每个 Sk，使用映射查找每个所需字符的下一次出现(如果存在)。

这实际上是在制作一个确定性有限自动机，它匹配 t ( https://en.wikipedia.org/wiki/Deterministic_finite_automaton ) 的子序列。