java - 实现 Java 的 indexOf 方法(子串搜索)

Question

我只是第二学期的 CS 学生，不会使用任何众所周知的高效子字符串搜索算法。我需要使用以下方法签名实现 indexOf 方法:

int indexOf(String str, String pattern) 返回 pattern 作为 str 的子字符串出现的第一个位置的索引。

这是我尝试过的:

首先，我创建了一个重载方法 index of，其签名为 indexOf(String str, char ch, int startIndex)，它返回 char 第一个位置的索引，否则返回 -1。

 private int indexOf(String str, char ch, int startIndex) {
    for(int i = startIndex; i < str.length(); i++)
        if(str.charAt(i) == ch) return i;

    return -1;
}

现在我编写了搜索子字符串 (pattern) 的方法。

private int indexOf(String str, String pattern) {
    int headIndex = indexOf(str, pattern.charAt(0), 0);
    int tailIndex = indexOf(str, pattern.charAt(pattern.length() - 1), 0);

    if(headIndex == -1 || tailIndex == -1) return -1; // no substring match

    while(true) {
        int j = 0;
        for(int i = headIndex; i <= tailIndex; i++)
            if(str.charAt(headIndex) != pattern.charAt(j++)) { //if substring does not match then compute a new head and tail Index
                headIndex = indexOf(str, pattern.charAt(0), headIndex);
                tailIndex = indexOf(str, pattern.charAt(pattern.length() - 1), tailIndex);
                j = 0;
                i = headIndex + 1;
                if(headIndex == -1 || tailIndex == -1) return -1;
                break;
            }

        if(headIndex >= 0) return headIndex;
    }
}

我相信我已经很接近了，但是像 indexOf("Hellolo", "lo") 这样的调用返回 2 而不是 3。我想弄清楚我的逻辑和需要哪里出了问题帮助这样做。

我不允许使用除长度之外的任何特殊字符串方法。

Answer 1

在您的代码中，您正在寻找单个字符而不是字符串的第一个索引。

int headIndex = indexOf(str, pattern.charAt(0), 0);

如果我们假设 str = Hello" 和 pattern = "lo" 那么上面的代码正在寻找 l 而不是lo.

编辑:如果你想查找字符串 "lo" 的第一次出现，那么你必须将代码更改为

int headIndex = indexOf(str, pattern, 0);