Finding the N-th Occurrence of a Substring in a String in Java

1. 概述

在 Java 中处理字符串时，查找一个较长字符串中的子串是一个常见操作。通常，我们可以使用 indexOf() 方法找到子串的索引。

本教程将探讨解决一个有趣且实用的问题：在一个大字符串中找到子串的第 n 次出现。我们将探索不同的方法来实现这一目标。

2. 问题介绍

标准的 indexOf() 方法可以给我们提供子串在字符串中的索引。例如，在 "This is a word." 中找到子串 "a" 的索引（8）：

int firstIdx = "This is a word.".indexOf("a");
assertEquals(8, firstIdx);

然而，indexOf(substring) 方法总是返回子串第一次出现的索引。因此，当我们想要使用这种方法获取子串的第 n 次出现的索引时，有时会有些不便。看下面的例子：

final static String INPUT = "a word, a word, a word, a word";
// indexes of "a":          "0       8       16      24 "

如上所述，输入字符串 INPUT 包含四个 "a"。直接调用 indexOf("a") 可以得到第一个 "a" 的索引（0）。但我们需要解决方案来获取其他 "a" 出现的其他索引，比如 8、16 和 24。

接下来，我们看看如何解决这个问题。

为了简化，我们将使用单元测试断言来验证每个方法是否返回预期结果。

3. 查找子串的第二次出现

在解决“查找第 n 次出现”问题之前，让我们先找到子串 "a" 的第二次（n=2）出现的索引。然后，我们将扩展“查找第二次出现”的解决方案，以适用于各种“第 n 次出现”问题。

我们知道 indexOf("a") 返回 "a" 的第一次出现的索引。此外，我们可以通过传递 fromIndex 整数参数给 indexOf() 方法。fromIndex 参数表示我们从哪个字符位置开始搜索。

因此，一个直接的想法是调用两次 indexOf() 来获取第二次出现的索引：

调用 indexOf(substring) 获取第一次出现的索引，并将其保存在变量中，例如 firstIdx
调用 indexOf(substring, firstIdx + substring.length()) 获取第二次出现的索引

现在，让我们实现这个方法，并使用我们的 INPUT 字符串进行测试：

int firstIdx = INPUT.indexOf("a");
int secondIdx = INPUT.indexOf("a", firstIdx + "a".length());
assertEquals(8, secondIdx);

可能有些人已经意识到，我们可以调用 indexOf() n 次，每次传递相应的 fromIdx 参数，来获取第 n 次出现的索引。例如，上面的测试可以添加另一个 indexOf() 调用来获取第三次出现的索引：thirdIdx = INPUT.indexOf("a", secondIdx + "a".length());。

那么，让我们扩展“查找第二次出现”的解决方案到“查找第 n 次出现”。

4. 查找子串的第 n 次出现

通常，我们会使用递归或循环来实现重复操作。

4.1. 递归方法

首先，我们实现递归解决方案：

int nthIndexOf(String input, String substring, int nth) {
    if (nth == 1) {
        return input.indexOf(substring);
    } else {
        return input.indexOf(substring, nthIndexOf(input, substring, nth - 1) + substring.length());
    }
}

实现相当直观。nth 变量作为计数器，在每次递归步骤中减少其值。

接下来，用示例数据测试该方法：

int result1 = nthIndexOf(INPUT, "a", 1);
assertEquals(0, result1);

int result2 = nthIndexOf(INPUT, "a", 2);
assertEquals(8, result2);

int result3 = nthIndexOf(INPUT, "a", 3);
assertEquals(16, result3);

int result4 = nthIndexOf(INPUT, "a", 4);
assertEquals(24, result4);

int result5 = nthIndexOf(INPUT, "a", 5);
assertEquals(-1, result5);

如果运行测试，它会通过。而且，正如我们所见，当总出现次数小于 nth 值时，方法会返回 -1。

4.2. 迭代方法

同样，我们可以在迭代方法中实现相同的思想：

static int nthIndexOf2(String input, String substring, int nth) {
    int index = -1;
    while (nth > 0) {
        index = input.indexOf(substring, index + substring.length());
        if (index == -1) {
            return -1;
        }
        nth--;
    }
    return index;
}

使用相同的输入进行测试也通过了：

int result1 = nthIndexOf2(INPUT, "a", 1);
assertEquals(0, result1);

int result2 = nthIndexOf2(INPUT, "a", 2);
assertEquals(8, result2);

int result3 = nthIndexOf2(INPUT, "a", 3);
assertEquals(16, result3);

int result4 = nthIndexOf2(INPUT, "a", 4);
assertEquals(24, result4);

int result5 = nthIndexOf2(INPUT, "a", 5);
assertEquals(-1, result5);

5. 正则表达式解决方案

我们已经了解了如何使用 indexOf() 方法解决问题。另一种选择是使用 Java 的正则表达式 API。

Matcher.find() 方法允许我们在输入字符串中找到下一个匹配的出现。因此，我们可以调用 Matcher.find() n 次来获取第 n 次匹配。同时，我们可以使用 Matcher.start() 获取每次匹配的起始索引：

int nthOccurrenceIndex(String input, String regexPattern, int nth) {
    Matcher matcher = Pattern.compile(regexPattern).matcher(INPUT);
    for (int i = 0; i < nth; i++) {
        if (!matcher.find()) {
            return -1;
        }
    }
    return matcher.start();
}

接下来，创建一个测试来验证基于正则表达式的解决方案是否正确工作：

int result1 = nthOccurrenceIndex(INPUT, "a", 1);
assertEquals(0, result1);

int result2 = nthOccurrenceIndex(INPUT, "a", 2);
assertEquals(8, result2);

int result3 = nthOccurrenceIndex(INPUT, "a", 3);
assertEquals(16, result3);

int result4 = nthOccurrenceIndex(INPUT, "a", 4);
assertEquals(24, result4);

int result5 = nthOccurrenceIndex(INPUT, "a", 5);
assertEquals(-1, result5);

值得注意的是，这种解决方案允许我们在输入中匹配符合模式的动态子串。然而，相比之下，基于 indexOf() 的方法仅适用于固定子串。

6. 总结

在这篇文章中，我们学习了在字符串中查找子串第 n 次出现的多种方法：

基于 indexOf() 方法的递归解决方案
基于 indexOf() 方法的迭代解决方案
正则表达式解决方案

如往常一样，示例代码的完整源代码可以在 GitHub 上找到。

Persistence

REST

Security