algorithm - 采访：如何验证一个字符串是否包含另一个字符串？

Question

一般的想法是做两个for循环，执行字符串1中的每个字符，比较string2中的每个字符，如果都找到，则表示包含。所以我们需要循环string1中的所有字符，并比较所有字符，看看string2中的所有字符，这将O sqaure运行时间。哪个面试官说这不是个好主意。

在它之后，我正在考虑它。我不能产生一个没有做两个循环的想法。也许我可以先从 string1 中获取所有字符，转换为 asc2，即内置到树中的数字。因此，当与 string2 进行比较时，它会使搜索非常快。

或者任何人有更好的主意？

就像 string1 是 abc 但 string2 是 cbattt 这意味着每个字符都包含在 string2 中。不是子字符串，

Answer 1

在文本中搜索给定模式（模式匹配）是一个众所周知的问题。已知解决方案：

1. KMP
2. 见证人表
3. 博耶摩尔
4. 后缀树

所有解决方案都在一些次要方面有所不同，比如它是否可以推广到 2D 模式匹配，或者更多。如果它需要预处理，如果它可以概括为未绑定的字母，运行时间等'......

编辑：
如果您只想知道某个字符串的所有字母是否都出现在其他字符串中，为什么不使用字母表大小的表格，指示是否可以在字符串中找到给定的字符。如果字母表无界或非常大（超过O(1)），请使用哈希表。

Answer 2

正如 iccthedral 所说，boyer moore可能是面试官想要的。