java - 比较两个未知字符串并找到匹配项

Question

如果我有

String x = "test";
String s = "tastaegasghet;

你可以在字符串 s 中找到 test。使用已知字符串执行此操作的简单方法如下:

.*t+.*e+.*s+.*t+.*

如果我们可以按顺序找到字母 t e s t 以及其间的任何字符，则返回 true。我想做同样的事情，但有两个未知的字符串 x 和 s，或者换句话说，字符串 s 和 x 可以是任何东西。我不需要硬编码的东西，而是通用的东西。

Answer 1

这是循环解决方案的伪代码:

function (
    needle, // x
    haystack // s
) {
    j = 0
    for (i = 0; i < haystack.length && j < needle.length; i++) {
         if (haystack[i] == needle[j]) {
             j++
         }
    }

    return j == needle.length
}

您只需要循环遍历 haystack 字符串中的每个字符，并在找到匹配的字符时将指针推进 Needle 字符串中。如果指针到达针串的末尾，则表示可以找到作为干草堆串的子序列的针串。

您可以做的一个小优化是检查 needle.length <= haystack.length在开始循环之前。

只是为了好玩

如果你想走克苏鲁的路，你可以使用这个结构:

(?>.*?t)(?>.*?e)(?>.*?s)(?>.*?t).*+

这不存在灾难性回溯的风险，并且应该与上面的循环类似(线性复杂性)，只是它在编译和匹配正则表达式方面有大量开销。