Return 查询作为 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"，query是"err"，那么输出应该是1，结果是0，代码哪里错了？顺便说一句，我不能在 String class.

之外使用方法

Answer 1

错误的是，您将 err 与：

进行比较

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

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

之间的比较

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

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

检查 query 在 src 中是否存在并循环直到 return 为假。每次出现时，获取 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 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是query在src中的索引，但是增量项使用了indexOf(String str, int fromIndex)，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.