使用函数搜索子字符串js

Question

我想用JavaScript语言写一段代码，搜索一个单词中字母的重复次数，就像下面的代码一样，但是用一种简短的方式o(n)

function naiveSearch(long, short){
var count = 0;
for(var i = 0; i < long.length; i++){
for(var j = 0; j < short.length; j++){
if(short[j] !== long[i+j]) break;
if(j === short.length - 1) count++;
}
}
return count;
}
naiveSearch("lorielol loled", "lol")

Answer 1

使用.substring()或.slice()方法，而不是嵌套循环。

function naiveSearch(long, short) {
var count = 0;
for (var i = 0, limit = long.length - short.length; i < limit; i++) {
if (long.substring(i, i + short.length) == short) {
count++;
}
}
return count;
}
console.log(naiveSearch("lorielol loled", "lol"));

仍然是O(n*m)主循环进行O(n)次迭代，子字符串和比较都是O(m)次。