java - 在java中编写自定义indexOf()方法

Question

我目前正在尝试调试为名为 MyString 的类编写的 indexOf() 方法。相关方法如下:

public int indexOf(int startIndex, char ch) 
{
    if(startIndex < 0 || startIndex >= length())
    {
        System.out.println("\nFATAL ERROR: indexOf() given invalid startIndex\n");
        System.exit(0);
    }
    for(int i = startIndex; i < this.length(); i++)
    {
        if(this.charAt(i) == ch)
        {
            return i;
        }
    }
    return NOT_FOUND;
}


public int indexOf(MyString key)
{   
    if(key.length() > this.length())
    {
        return NOT_FOUND;
    }
    int indexOfFirstKeyLetter = indexOf(0, key.letters[0]);
    while(indexOfFirstKeyLetter != NOT_FOUND)
    {
        if(keyFound(indexOfFirstKeyLetter, key))
        {
            return indexOfFirstKeyLetter;
        }
        else
        {
            indexOfFirstKeyLetter = indexOf(indexOfFirstKeyLetter + 1, key.letters[0]);
        }
    }
    return NOT_FOUND;
}


private boolean keyFound(int indexOfFirstKeyLetter, MyString key) //Note: this method works for most strings, but doesn't work if the end of MyString is identical to the first few letters of key (ex: ado and dog falsely returns as true)
{
    for(int i = indexOfFirstKeyLetter; i < key.length() + indexOfFirstKeyLetter && i < this.length(); i++)
    {
        if(this.letters[i] != key.letters[i - indexOfFirstKeyLetter])
        {
            return false;
        }
    }
    return true;
}

我相信问题出在我的 keyFound 方法上，虽然它适用于大多数字符串，但当正在测试的 MyString 对象的末尾与它所比较的​​键的前几个字母相同时，它将返回 true。例如，在indexOf(MyString other)方法中测试“ado”和“dog”时，它返回值1，表示在this.letters[1]位置找到匹配开头的索引，当它应该返回 NOT_FOUND 或 -1 时，因为完整的 key 字符串“dog”不在“ado”中。有什么方法可以改变我的 keyFound 方法来解决这个问题吗？

Answer 1

发生的情况是您到达字符串末尾并在检查整个比较字符串之前退出:

你的逻辑是:“ado”中是“dog”吗？在 'ado' 中查找第一个匹配 'd' 的索引，它是 1. "d"== "d"。很好，下一个字母，“o”==“o”。下一封信真好。等待。 'ado' 字符串完成。一定是被发现了。返回真。

您的 keyFound 函数需要一个提前退出条件，如果在搜索整个“key”的长度之前它已到达字符串末尾，则返回 false。

请注意，这比实际情况要复杂得多。您可以通过一个循环轻松完成此操作。现在您拥有的所有循环的时间复杂度为 O(n^3)。