面试题：Java中基于String实现高效子串查找逻辑

利用Java的String类及相关方法构建高效子串查找逻辑

indexOf方法：
- indexOf(String str) 方法用于返回指定子字符串在此字符串中第一次出现处的索引。如果没有找到，则返回 -1。
- 性能方面，它是基于朴素字符串匹配算法，时间复杂度在最坏情况下为 O(n * m)，其中 n 是原字符串的长度，m 是子串的长度。
- 适用场景：当子串较短且原字符串长度不是特别巨大时，indexOf 方法简单易用，性能也可接受。
- 代码示例：

public class SubstringSearch {
    public static void main(String[] args) {
        String largeText = "this is a very large text string";
        String targetSubstring = "large";
        int index = largeText.indexOf(targetSubstring);
        if (index != -1) {
            System.out.println("Substring found at index: " + index);
        } else {
            System.out.println("Substring not found");
        }
    }
}

contains方法：
- contains(CharSequence s) 方法用于判断此字符串是否包含指定的字符序列。它内部实际上调用了 indexOf 方法。
- 性能与 indexOf 类似，时间复杂度在最坏情况下为 O(n * m)。
- 适用场景：当只关心子串是否存在，而不关心其具体位置时，contains 方法语义更清晰，代码更简洁。
- 代码示例：

public class SubstringSearchContains {
    public static void main(String[] args) {
        String largeText = "this is a very large text string";
        String targetSubstring = "large";
        if (largeText.contains(targetSubstring)) {
            System.out.println("Substring found");
        } else {
            System.out.println("Substring not found");
        }
    }
}

优化建议：
- 预编译正则表达式：如果子串的查找规则比较复杂，例如包含通配符等，可以使用正则表达式。但直接使用 String 的 matches 方法性能较差，因为每次调用都会编译正则表达式。可以使用 Pattern 和 Matcher 类预编译正则表达式。
- 使用更高效的算法：对于非常大的文本和频繁查找操作，可以考虑使用更高效的字符串匹配算法，如KMP（Knuth - Morris - Pratt）算法。Java 中虽然没有直接提供 KMP 实现，但可以自己实现该算法来提升性能，KMP 算法时间复杂度为 O(n + m)。

不同场景下方法的选择

简单存在性判断：如果只需要判断子串是否存在于大文本中，contains 方法是首选，因为它语义清晰，代码简洁，虽然性能与 indexOf 类似，但代码可读性更好。
查找子串位置：如果需要获取子串在大文本中的位置，indexOf 方法是合适的选择。
复杂匹配规则：当子串的匹配规则复杂，如包含正则表达式的情况，预编译正则表达式并使用 Pattern 和 Matcher 类进行匹配。
超大规模文本频繁查找：对于超大规模文本且频繁查找操作，实现如KMP这样的高效算法会显著提升性能。

星途面试题库

面试题：Java中基于String实现高效子串查找逻辑

知识考点

面试题答案

利用Java的String类及相关方法构建高效子串查找逻辑

不同场景下方法的选择