0

我目前正在为一个类创建一个 TextLine 类的项目，该类表示必须表示为字符数组的一行文本。我不允许以任何方式间接或直接使用字符串类来表示 TextLine 对象，但是，我可以使用它来处理参数。

对于其中一种方法，我应该将一个字符串作为参数的参数，它也是TextLine对象的一个​​片段，然后返回该片段在这个TextLine中第一次出现的索引位置，或者- 1，如果没有找到片段。

现在，我正在尝试找出 indexOf 方法，但我的问题是我的方法只检查一次起点。因此，如果 TextLine 对象的字母第一次与片段的字母不匹配，但在对象的其他位置有另一个匹配项，则该方法不会检查该起点。

例如，假设我输入 penplay 作为 TextLine，然后输入 play 作为片段。显然，TextLine 中出现了 play，但是我的 indexOf 方法所做的是，它检查 penplay 中索引 0 处的第一个 p，然后继续查看以下字母是否与 play 长度匹配，如果它没有，它返回-1。知道如何让算法继续寻找另一个起点吗？

这就是我的代码：

public int indexOf(String fragment){

char[] temp = fragment.toCharArray();

int j = 0;
for(int i = 0; i < someText.length; i++){
    while(someText[i] == temp[j]){

        for(j = 1; j < temp.length; j++){
            if(temp[j] != someText[i+j]){
                return -1;
            }
        }

        return i;

    }
}

return -1;

}
4

3 回答 3

4

当没有必要时，您正在对第一个字符进行特殊处理。基本上你需要说：

  • 对于每个潜在的起始角色...
    • fragment从那个候选位置开始，整个匹配吗？

所以像：

// Only deal with *viable* starting points
for (int i = 0; i < someText.length - temp.length; i++) {
    boolean found = true;
    for (int j = 0; j < temp.length && found; j++) {
        if (temp[j] != someText[i + j]) {
            found = false;
        }
    }
    if (found) {
        return i;
    }
}
return -1;

这可以通过提取内部循环来重构：

for (int i = 0; i < someText.length - temp.length; i++) {
    if (textMatches(temp, i)) {
        return i;
    }
}
return -1;

...
// TODO: Javadoc to explain parameters :)
private boolean textMatches(char[] chars, int startingIndex) {
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != someText[i + startingIndex]) {
            return false;
        }
    }
    return true;
}
于 2011-07-13T22:01:00.050 回答
1

您设置它的方式似乎适合作为一种doesStringExistAtIndex(j, fragment)功能。如果字符串在第一个索引处不存在，则返回 -1，因此您可以执行以下操作：

//assuming that "this" is the subject that you are searching in
public int indexOf(String fragment){
  for(int i=0; i<this.length; ++i){
    if(doesStringExistAtIndex(i, fragment))
      return i;
  }
  return -1;
}
于 2011-07-13T22:02:11.280 回答
0

不确定这是否是您想要的，但我基本上写了一个 indexOf 方法。我做了一些测试，在我做的一些测试中它似乎工作得很好。当然，它看起来会有所不同，因为我想让测试更容易，但如果你决定使用它，转换时间应该是 30 秒或更短。

public int indexOf(String fragment, String source)
{
    char[] temp = fragment.toCharArray();
    char[] someText = source.toCharArray();

    outer : for(int i = 0; i <= someText.length - temp.length;i++) //stops looping because why loop after the fragment is longer than the source we have left when its impossible to find
    {
        if(someText[i] == temp[0]) //if the first characters are the same
        {
            int q = 0;
            while(q < temp.length) //loop through the fragment
            {
                if(someText[i+q] != temp[q]) //if the characters are not the same, stop, and go to the next character of the source. Don't return anything
                {
                    continue outer; //continues the loop labeled 'outer' (e.g. outer : for(...) )
                }
                q++; //increment index since they both match
            }
            return i; //fragment and some part of the source matched since it reached here. Return the index of the first character
        }
    }
    return -1; //reached here because nothing was found :( return -1
}

编辑 0添加行注释

于 2011-07-13T22:19:19.737 回答