java返回查询作为src的子字符串出现的次数

Question

/** Return the number of times query occurs as a substring of src
 * (different occurrences may overlap).
 * Precondition: query is not the empty string "".
 * Examples: For src = "ab", query = "b", return 1.
 *           For src = "Luke Skywalker", query = "ke", return 2.
 *           For src = "abababab", query = "aba", return 3.
 *           For src = "aaaa", query = "aa", return 3.*/
public static int numOccurrences(String src, String query) {
    /* This should be done with one loop. If at all possible, don't have
     * each iteration of the loop process one character of src. Instead,
     * see whether some method of class String can be used to jump from one
     * occurrence of query to the next. */
    int count = 0;
    for (int i = 0; i < src.length(); i++) {
        int end = i + query.length() - 1;
        if (end < src.length()) {
            String sub = src.substring(i, end);
            if (query.contentEquals(sub)) 
                ++count;
        } 
    }return count;
}

我测试了代码。如果src是“cherry”，查询是“err”，那么输出应该是1，但结果是0。代码怎么了？顺便说一句，我不能在String类之外使用方法

Answer 1

检查src中是否存在query并循环，直到返回false。每次出现时，取substring，更新count并重复，直到在src中找不到query

伪代码：

int count = 0;
loop (flag is true) 
  int index = find start index of query in src;
  if (query is found) 
    src = update the src with substring(index + query.length());
    count++;
  else 
    flag = false;      
return count;

Answer 2

伪代码：

init 'count' and 'start' to 0
while true do
  find first occurence of 'query' in 'source', start search at 'start'
  if found
    set 'start' to found position + 1
    set count to count + 1
  else
    break out of while loop
end while
return count

提示：在source中查找query时使用String#indexOf(String str, int fromIndex)

Answer 3

错的是，您将err与以下内容进行比较：

i | sub
--|------
0 | ch
1 | he
2 | er
3 | rr

请注意，您正在比较的这些字符串看起来很短，在停止检查匹配项之前，您甚至还没有到达“cherry”的末尾。因此，您需要在代码中解决两件事：计算end的方式以及end和src.length()之间的比较

提示：substring的第二个参数（结束索引）是独占的

Answer 4

这就是工作：

public static int numOccurrences(String src, String query) {
    int count = 0;
    for(int i = src.indexOf(query); i > -1;i = src.indexOf(query, i + 1)) 
        count++;
    return count;
}

这里，i是src中query的索引，但是增量项使用了^{}，javadoc说：

Returns the index within this string of the first occurrence of the specified substring, starting at the specified index.

它被传递索引i加上1，以开始搜索上一次命中后的另一个事件

这也解决了评论中暗示的NFR：

Instead, see whether some method of class String can be used to jump from one occurrence of query to the next.