java - 查找字符串是否包含没有 Java.substring 的子字符串

Question

Design a function hasCheated(String s1, String s2, int N) that returns true if the two strings, s1, s2 have a common substring of at least length N. Without using .contains, .substring

是否需要转换为 char 数组或类似的方法？

我正在考虑寻找最长公共(public)子串，然后再看N。对此有哪些方法？

Answer 1

首先找到最长的公共(public)子串比仅仅检查是否存在至少给定大小的匹配要慢。您可以在找到匹配项后立即停止，即使可能有更长的匹配项也是如此。

我会构建一个散列集(如果要求更复杂，则为散列映射)，它代表一个长度为 N 的所有子字符串(而不实际创建这些子字符串)，并使用它来扫描长度为 N 的字符串匹配。

您可以在 O(M) 时间内完成此操作，其中 M 是最长字符串的长度。

您可以像这样创建一个子字符串类。

class Substring {
    final String s;
    final int offset, length, hashCode;

    Substring(String s, int offset, int length) {
        this.s = s;
        this.offset = offset;
        this.length = length;
        this.hashCode = hashCode(s, offset, length); // define to taste
    }

    public int hashCode() { return hashCode; }

    public boolean equals(Object o) {
       if (!(o instanceof Substring)) return false;
       Substring ss = (Substring) s;
       if (hashCode != ss.hashCode || length != ss.length) return false;
       for (int i = 0; i < length; i++) 
           if (s.charAt(i) != ss.s.charAt(i))
               return false;
       return true;
    }
}

要构建 HashSet，您可以在 O(n) 中执行以下操作，其中 n 是 s1.length()

Set<Substring> substrings = new HashSet<>();
for (int i = 0; i < s1.length() - n; i++) {
    Substring ss = new Substring(s1, i, n);
    substrings.add(ss);
}

要搜索匹配项，您可以在 O(n) 中执行以下操作，其中 n 是 s2.length()

for (int i = 0; i < s2.length() - n; i++) {
    Substring ss = new Substring(s2, i, n);
    if (substrings.contains(ss))
         return true; // found a match.
}