第 71 题：实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。 #119

ZodiacSyndicate · 2019-05-10T01:06:10Z

const find = (S, T) => {
  if (S.length < T.length) return -1
  for (let i = 0; i < S.length; i++) {
    if (S.slice(i, i + T.length) === T) return i
  }
  return -1
}

jjeejj · 2019-05-10T01:13:42Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) return i ;
  };
  return -1;
};

keiseiTi · 2019-05-10T02:21:55Z

const find = (S,T) => S.indexOf(T)

sgzhm4444 · 2019-05-10T02:29:41Z

var position = [];

const find = (S, T) => {
	if (S.length < T.length) {
		position.push(-1);
	} else {
		for (let i = 0; i < S.length; i++) {
			if (S.slice(i, i + T.length) === T) {
				position.push(i);
			}
		}
	}
}

find(S,T);

JayZangwill · 2019-05-10T03:06:22Z

// 方法一：
const find = (S, T) => S.search(T)

// 方法二：
const find = (S, T) => {
  const matched = S.match(T) 
  return matched ? matched.index : -1 
}

Vdan123 · 2019-05-10T03:09:45Z

var find = function(S,T){

  if(T.length > S.length) return -1;
    
  let index = S.indexOf(T);
  let count = [];

  while(index != -1){
    count.push(index);
    index = S.indexOf(T,index + T.length);
   }

    return count;

}

indexOf 可以直接返回字符串所在的位置，但同时是否需要考虑，如果T在S中重复出现的，需要将两个位置都展示出来？

FishPlusOrange · 2019-05-10T04:02:38Z

我的核心思想是使用 split，假设未匹配到返回-1：

let findIndex = (S, T) => {
  let index = -1
  if (!T.length || T.length > S.length) return index // T 为空字符串或 T 的长度大于 S 均直接返回-1
  const arr = S.split(T)
  if (arr.length > 1) index = arr[0].length
  return index
}

findIndex('FishPlusOrange', 'Plus') // 4
findIndex('FishPlusOrange', 'sulP') // -1

需要注意的是，在以上算法中，如果字符串 S 中存在多个字符串 T，仅返回第一个的位置

kingstone3 · 2019-05-10T04:15:34Z

function e(s, t){
  let reg = new RegExp(t, 'g');
  let tArray = [];
  let result = [];
  while((tArray = reg.exec(s)) !== null){
     result.push(tArray.index);
  }
  
  return result;
}

FounderIsShadowWalker · 2019-05-10T05:11:09Z

function Test(s, t){
if(s.length < t.length){
return -1;
}else{
return s.indexOf(t);
}
}

LiuMengzhou · 2019-05-10T05:12:26Z

用了API的是不是不太体面？

  getIndexOf = function (s, t) {
    let n = s.length;
    let m = t.length;
    if (!n || !m || n < m) return -1;
    for (let i = 0; i < n; i++) {
      let j = 0;
      let k = i;
      if (s[k] === t[j]) {
        k++; j++;
        while (k < n && j < m) {
          if (s[k] !== t[j]) break;
          else {
            k++; j++;
          }
        }
        if (j === m) return i;
      }
    }
    return -1;
  }

LiuMengzhou · 2019-05-10T05:25:29Z

我的核心思想是使用 split，假设未匹配到返回-1：
let findIndex = (S, T) => {
  if (!T.length || T.length > S.length) return -1 // T 为空字符串或 T 的长度大于 S 均直接返回-1
  return S.split(T)[0].length
}

findIndex('FishPlusOrange', 'Plus') // 4
需要注意的是，在以上算法中，如果字符串 S 中存在多个字符串 T，仅返回第一个的位置

@FishPlusOrange

Tangjj1996 · 2019-05-10T05:54:53Z

我的核心思想是使用 split，假设未匹配到返回-1：
let findIndex = (S, T) => {
  if (!T.length || T.length > S.length) return -1 // T 为空字符串或 T 的长度大于 S 均直接返回-1
  return S.split(T)[0].length
}

findIndex('FishPlusOrange', 'Plus') // 4
需要注意的是，在以上算法中，如果字符串 S 中存在多个字符串 T，仅返回第一个的位置

你这种方法没有考虑S不存在T的情况，按你这种方法如果不存在的话，返回的是S的长度

FishPlusOrange · 2019-05-10T06:53:53Z

@LiuMengzhou @Tangjj1996 感谢提醒，已经改正

goodwinfame · 2019-05-10T08:49:21Z

请问下这题主要考什么？为啥indexOf不行？

cheungkin24 · 2019-05-13T07:26:40Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) return i ;
  };
  return -1;
};

循环条件要改成这样吧

i < S.length - T.length + 1

LiuL0703 · 2019-05-15T14:41:30Z

我觉得是考KMP算法吧

ZhangMingZhao1 · 2019-05-15T15:45:00Z

var S, T;
var next = [];

// 预计算next数组
function getNext() {
	let k = -1,
		j = 0;
	next[0] = -1;
	while (j < len_t) {
		if (k == -1 || T[j] == T[k]) {
			++j;
			++k;
			next[j] = k;
		} else k = next[k];
	}
}

// 返回子串首次出现的位置
function KMP_Index() //T是模式串，S是 主串 
{
	let i = 0,
		j = 0;
	getNext();
	while (j < len_t && i < len_s) {
		if (j == -1 || T[j] == S[i]) {
			i++;
			j++;
		} else j = next[j];
	}
	if (j == len_t) {
		return i - len_t;
	} else return -1;
}

//返回子串出现的次数
function KMP_Count() {
	let ans = 0;
	let i = 0,
		j = 0;

	getNext();
	for (i = 0; i < len_s; i++) {
		while (j > 0 && T[j] != S[i]) {
			j = next[j];
		}
		if (T[j] == S[i]) j++;
		if (j == len_t) {
			ans++;
			j = next[j];
		}
	}
	return ans;
}

S = "123454321";
T = "0"
len_s = S.length;
len_t = T.length;

//KMP_Index()如果为-1则没有匹配
console.log(`主串为${S},模式串为${T},模式串首次出现的位置为${KMP_Index()},出现的次数为${KMP_Count()}`);

本质上为KMP算法或者KMP的优化，只要理解next数组的意义和推导，字符串匹配的题目万变不离其宗。

（附上很早之前做的这个算法的PPT链接。。。
http://note.youdao.com/noteshare?id=91749237e787b4aa0b246336ea0c1137 ）

ckjie · 2019-06-24T13:39:42Z

const find = (S, T) => {
  const indexList = [];
  if(S.length < T.length) return -1;
  for(let i = 0; i <= S.length - T.length; i++) {
    if(S.slice(i, i + T.length) === T) indexList.push(i)
   }
  return indexList.length? indexList : -1;
}

dorseysen · 2019-06-27T09:14:45Z

//  考查indexOf
const includeString = (parent, child) => parent.indexOf(child);

console.log( includeString('hello, my name is dorsey', 'dorsey') );

dongj0316 · 2019-06-27T10:54:19Z

搜索了一下KMP算法：
https://zh.wikipedia.org/wiki/%E5%85%8B%E5%8A%AA%E6%96%AF-%E8%8E%AB%E9%87%8C%E6%96%AF-%E6%99%AE%E6%8B%89%E7%89%B9%E7%AE%97%E6%B3%95

// 应该...没有bug吧^^
function getIndex (S, T) {
  const n = S.length;
  const m = T.length;
  if (n < m) {
    return -1;
  }
  if (n === m) {
    return S === T ? 0 : -1;
  }

  const start = T[0];
  const end = T[m - 1];
  let i = 0;

  while (i < n) {
    if (n - i < m) {
      return -1;
    }

    const currS = S[i];
    const currSEnd = S[i + m - 1];
    let mathing = true;

    if (currS !== start || currSEnd !== end) {
      i++;
      continue;
    }

    let j = 0;
    let step = 0;

    while (j < m) {
      const currS = S[i + j];
      const currSEnd = S[i + j + m - 1];
      const isEnd = j === m - 1;

      if (mathing) {
        const currW = T[j];
        mathing = currS === currW;

        if (mathing && isEnd) {
          return i
        }
      }
      
      if (!mathing && step !== 0) {
        break;
      }

      if (j > 0 && step === 0) {
        if (isEnd) {
          step = m;
        }
        if (currS === start && currSEnd === end) {
          step = j;
        }
      }
      j++;
    }
    i += step || 1;
  }

  return -1;
}

libin1991 · 2019-07-09T16:06:30Z

var a='abcdefghijkl'
var b='ghi'
var aL=a.length;
var bL=b.length;

function indexOf(str,item){
	for(var i=0;i<=aL-bL;i++){
		if(str.slice(i,bL+i)==item){
			return i
		}
	}
}

console.log(indexOf(a,b))

function idnexOf(a,b){
	var reg=new RegExp(`${b}`,'gi');
	var c=reg.exec(a);
	console.log(c ? c.index : -1)
}

var a = 'abcdefghijkl'
var b = 'jkl'
idnexOf(a,b)

xyxiao001 · 2019-07-12T06:12:53Z

hudie09143672 · 2019-07-12T07:47:37Z

function findStr(str, f){
var reg = new RegExp(f, 'g');
return reg.exec(str).index;
};

qiannianchong25 · 2019-07-26T13:05:47Z

呃，String.prototype.indexOf的功能不就是干这个的么？

dengshangli · 2019-07-29T12:14:56Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) return i ;
  };
  return -1;
};

这里S.length - T.length有点小错误，应该改为S.length

ZYSHINee · 2019-07-30T03:23:49Z

const strA = "qwertyuiopasfghjkasdflzxcvbnm";

const strB = "asdf";

function findStr(str1, str2) {
    const len = str2.length;
    const indexArr = [];
    str1.split("").forEach((v, i) => {
        if (v === str2[0]) indexArr.push(i);
    });
    let result;
    if (!indexArr.length) return "不存在相同的字符串";
    indexArr.forEach(idx => {
        result = str1.slice(idx, idx + len) === str2 ? idx : null;
    });
    return result;
}

console.log(findStr(strA, strB));

Stevendwy · 2019-08-01T06:50:16Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  // 包含多个该元素
  let ilist = []
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) ilist.push(i);
  };
  let _returnIndex = ilist.length < 1 ? -1 : ilist
  return _returnIndex;
};

SpengF · 2019-08-02T03:16:30Z

最高票的答案写的很好，不过还是不知道为啥不能用indexOf？因为面试题用indexOf太low了么?还是考察点不在这上

montage-f · 2019-08-02T08:23:03Z

const find = (S,T) => S.indexOf(T)

这个实现的有问题?

montage-f · 2019-08-02T08:24:18Z

最高票的答案写的很好，不过还是不知道为啥不能用indexOf？因为面试题用indexOf太low了么?还是考察点不在这上

我也想知道这个问题, 难道indexOf 不能实现?

coveyz · 2020-01-06T09:40:50Z

const findStr = (str, t) => {
	if (t.length > str.length) return -1;
	for (let index = 0; index < str.length - t.length + 1; index++) {
		const cur = str.slice(index, index + t.length);
		if (cur === t) {
			return index;
		}
	}
};

console.log(find('asdfg', 'sdf'));

shenxuxiang · 2020-02-05T01:09:58Z

function search(str, str1) {
    if (str.includes(str1)) {
        return str.indexOf(str1);
    } else {
        return -1;
    }
}

SerinaJingyiLu · 2020-03-05T15:05:39Z

首先是用了slice的这个贼简单：

function matching(n, str, m, match){
	if(m>n){
		return -1;
	}

	for(let i = 0; i<n-m+1; i++){
		if(str.slice(i,i+m)===match){
			return i;

		}
	}
	return -1;
}

然后我也记得我本科的时候算法课专门有节课讲了pattern matching 回去找了下课件果然是KMP 我结合了阮老师的这个http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 下面是我KMP的写法：

function partialMatchTable(str, n){
	let res = [0];
	let k = 0;
	for(let i=1; i<n; i++){
		while(k>0&&str[k]!==str[i]){
			k = res[k-1];
		}
		if(str[k]===str[i]){
			k += 1
		}
		res.push(k);

	}
	return res;

}

function KMP(n, str, m, match){
        if(m>n) return -1;
	let index = 0;
	let table = partialMatchTable(match, n);
        console.log(table);
	while(index<n){
		let same = 0;
		let index2 = 0;
		while(str[index+index2]===match[index2]&&index2<m){
			same += 1;
			index2 += 1;
		}
		if(same===m){
			return index;
		}
        if(same===0){
        	index += 1;
        }else{
        	index += same - table[same-1];
        }

	}
	return -1;
}

console.log(KMP(15, "ABDCABABDCABDCB", 7, "ABDCABD"))

结果在这里哈：

欢迎指正！！

dleged · 2020-03-20T03:33:18Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) return i ;
  };
  return -1;
};

@jjeejj

匹配到最后下标时候，find('123456','456') 为 -1，正确的值应该3；
for (let i = 0; i < S.length - T.length ; i++) 中的i < S.length - T.length 少了👆的情况，改为i <= S.length - < T.length即可

litokele2018 · 2020-03-25T09:19:23Z

//  使用KMP实现  KMP 原理就是 减少text 串的 重复遍历 一次结束 时间复杂度O(m + n)

function KMP(pattern, text) {
  let n = pattern.length
  let m = text.length
  // 计算pattern 的prefix 数组
  let arr = new Array(n).fill(0)
  let i = 0
  let j = 1
  while (j < n) {
    if (pattern[i] === pattern[j]) {
      arr[j] = i + 1
      i ++ 
      j ++ 
    } else if (i === 0) {
      j ++
    } else {
      i = arr[i - 1]
    }
  }
  // 进行 比较查找
  let h = 0
  let k = 0
  let count = 0
  while (k < n) {
    if (text[h] === pattern[k]) {
      h ++
      k ++
      count ++ 
    } else if (k !== 0) {
      k = arr[k - 1] 
      count = 0
    } else {
      h ++
      count = 0
    }
  }

  if (count === n) {
    return h - n
  }
}

let text = 'acbacbabcbcabcabcbcabca' // 11
let pattern = 'abcabcb'
console.log(KMP(pattern, text))

coveyz · 2020-04-22T06:15:48Z

const findStr = (str, t) => {
	if (t.length > str.length) return -1;
	for (let index = 0; index < str.length - t.length + 1; index++) {
		const cur = str.slice(index, index + t.length);
		if (cur === t) {
			return index;
		}
	}
};

wubing0324 · 2020-05-07T01:46:56Z

function findIdxs(S, T) {
  if (S.length < T.length) return []
  var reg = new RegExp(T, 'g')
  var arr = []
  do {
    var str = reg.exec(S)
    if (str && str.index > 0) {
      arr.push(str.index)
    }
  } while (str && str.index > 0);

  return arr
}
var S = 'hkjhkabclkkabcjk'
var T = 'abc'
console.log(findIdxs(S, T))

snowBoby · 2020-05-31T13:50:30Z

function searchIndex(s,t){
let i = 0;
let j = 0;
let idx = -1;
while(s.length-i >= t.length - j && j !== t.length){
if(s[i]===t[j]){
if(j==0){
idx = i;
}
j++;
}else{
idx = -1;
}
i++;
}
return idx;
}

jakesamz · 2020-06-13T16:06:25Z

最高票的答案写的很好，不过还是不知道为啥不能用indexOf？因为面试题用indexOf太low了么?还是考察点不在这上

我觉得是问题是想问 indexof 的实现算法，不是 api 的运用。

xueshuai · 2020-06-26T12:48:02Z

// 暴力破解
let text = 'ABABABCABAAABABABABCABAA'
let pattern = 'ABABCABAA'
function findSubString(s, t) {
  const n = s.length
  const m = t.length
  if(m > n) return ''
  if(s === t) return s
  let index = 0
  let i = 0, j = 0
  while(i < n) {
    while (j < m) {
      if(j === m - 1 && s[i] === t[j]) {
        console.log(`找到了匹配的位置索引是：${i - j}`)
        j = 0
        index ++
        i = index
      }
      if(s[i] === t[j]) {
        i++
        j++
      } else {
        j = 0
        index ++
        i = index
      }
    }
  }
}
findSubString(text, pattern)

// KMP算法
let text = 'ABABABCABAAABABABABCABAA'
let pattern = 'ABABCABAA'
function findPrefixTable (pattern) {
  let prefixTable = [0]
  let m = pattern.length
  let preLen = 0
  let i = 1
  while (i < m) {
    if(pattern[i] === pattern[preLen]) {
      preLen++
      prefixTable[i] = preLen
      i++
    } else {
      if(preLen > 0) {
        preLen = prefixTable[preLen - 1]
      } else {
        prefixTable[i] = preLen
        i++
      }
    }
  }
  return prefixTable
}
function movePreFixTable(prefixTable) {
  const temp = prefixTable
  temp.unshift(-1)
  temp.pop()
  return temp
}

function kmpSearch(text, pattern) {
  let n = text.length
  let m = pattern.length
  let i = 0, j = 0
  let prefixTable = movePreFixTable(findPrefixTable(pattern))
  while (i < n) {
    if(j === m - 1 && text[i] === pattern[j]) {
      console.log(`找到了匹配的位置索引是：${i - j}`)
      j = prefixTable[j]
    }
    if(text[i] === pattern[j]) {
      i++
      j++
    } else {
      j = prefixTable[j]
      if(j === -1) {
        i++
        j++
      }
    }
  }
}
kmpSearch(text, pattern)

xiaofangnihao · 2020-07-17T09:39:55Z

// 因为 T 的 length 是一定的，所以在循环S的的时候 ，循环当前项 i 后面至少还有 T.length 个元素
const find = (S, T) => {
  if (S.length < T.length) return -1;
  for (let i = 0; i < S.length - T.length ; i++) {
      if (S.substr(i, T.length) === T) return i ;
  };
  return -1;
};

for循环里的i应该小于S.length-T.length+1吧。您看看，是我理解错了还是您漏写了

89466598946659 · 2020-08-23T09:46:33Z

简单点的：
1、'abcde'.indexOf('bc');
2、'abcde'.search('bc');
3、'abcde'.match('bc');
4、for循环查找m位是否相等

Gcalolin · 2020-08-27T10:20:22Z

function findStr(S, T) {
  let currentIndex = 0
  let patch = []
  let reg = new RegExp(T)
  while(match = reg.exec(S)) {
    patch.push(match.index+ currentIndex)
    let index = match.index + T.length
    S = S.slice(index)
    currentIndex = index
  }
  return patch
}
findStr(S,T)

orime · 2021-01-30T09:10:25Z

一行搞定，注意要先判断S是否完整包含T，使用includes即可

```javascript
function findStr(S, T){
  return S.includes(T) ? S.indexOf(T) : -1
}

测试

const S1 = 'abcdefg', T1 = 'cde', T2 = 'fgh'
console.log(findStr(S1, T1)) // 2
console.log(findStr(S1, T2)) // -1

ghost · 2021-02-23T11:40:11Z

调用API的话就search方法

function findIndex(str, target) {
            return str.search(target);
        }

滑动窗口方法：

function findIndex(str, target) {
            let need = {}, window = {};
            for (let item of target) {
                window[item] = 0;
                need[item] ? (need[item]++) : (need[item] = 1);
            }
            let left = 0, right = 0;
            let valid = 0; // 表示窗口中满足need条件的字符个数，如果valid等于need的大小，说明窗口已经满足条件，目标子串已全部覆盖
            let needLen = Object.keys(need).length;
            while (right < str.length) {
                // c是即将移入窗口的字符
                let c = str[right];
                // 右移窗口
                right++;
                // 进行窗口内数据的一系列更新
                if (need[c]) { // 如果即将移入窗口的字符是有效字符
                    window[c]++;
                    // 如果窗口内命中字符出现次数和需求中一样，有效标记++
                    if (window[c] === need[c]) {
                        valid++;
                    }
                }
                // 判断左侧窗口是否要收缩
                while (right - left >= target.length) {
                    if (valid === needLen) {
                        return left;
                    }
                    // 将要移出窗口的字符
                    let d = str[left];
                    left++;
                    // 移出窗口所导致的一系列数据更新
                    if (need[d]) {
                        if (need[d] === window[d]) {
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
            return str[left] === target[0] ? left : -1;
        }

shuai4983958 · 2021-03-03T09:33:33Z

`function isExitF(total, small) {
let isExit = false
let left = 0
let right = small.length
while (right <= total.length) {
let currentStr = total.substring(left, right)
console.log(currentStr)
if (currentStr === small) {
return true
} else {
left += 1
right += 1
}
}

return isExit

}`

xiaocongWang · 2021-04-27T04:03:33Z

/**
 * 字符串匹配，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置
 * 遍历 S，找出 S 和 T 第一个字符相同的位置 i，比较 i 到 i + T.length 这部分字符串是否 === T；如果不相同，则继续下一个字符；当遍历到 S 剩下的字符串长度小于 T 的长度，则退出循环
 */
function find(S, T) {
    for (let i = 0; i <= S.length - T.length; i++) {
        if (S[i] !== T[0]) {
            continue;
        }
        if (S.slice(i, i + T.length) === T) return i + 1;
    }
    return -1;
}

console.log(find('sjdjsds', 'sds'));

haiyangzhishengs · 2021-07-07T02:22:57Z

应用正则应该是最简单的
S.match(eval('/'+T+'/')).index

hdsuperman · 2021-11-18T10:02:06Z

考虑性能的话 kmp 才是正解

Four-Names · 2022-02-24T09:36:40Z

let str1 = "hellomasd,asdasdasdan";
let str2 = "asdasdasdan";
let fun = (base, target) => {
  let conditionLen = base.length - target.length;
  for (let i = 0; i <= conditionLen; i++) {
    if (base[i] == target[0]) {
      let j = 1;
      while (j < target.length) {
        if (target[j] == base[i + j]) j++;
        else break;
      }
      if (j == target.length) return i;
    }
  }
  return -1;
};
console.log(fun(str1, str2));

yuerdev · 2022-06-28T09:12:08Z

请问下这题主要考什么？为啥indexOf不行？

你用indexOf,面试官会问你有没有其他解法，直到KMP结束😢

Lxming1 · 2022-08-08T11:05:09Z

function foo(target, fragment){
const frag = target.split(fragment)
if (frag.length >= 2){
return frag[0].length
}
return -1
}

89466598946659 · 2022-08-08T11:05:31Z

您的邮件已收到！O(∩_∩)O！--------Pan

benzhemin · 2023-02-24T06:54:16Z

const findSubstring = (fullStr, subStr) => {
    if (fullStr.length < subStr.length) return -1;

    for (let i = 0; i<fullStr.length - 1; i++) {
        if (fullStr.slice(i, subStr.length) === subStr) {
            return i;
        }
    }

    return -1;
}

xia0ming · 2023-04-07T03:43:50Z

KMP算法?

89466598946659 · 2023-04-07T03:44:09Z

您的邮件已收到！O(∩_∩)O！--------Pan

yinzuowen · 2024-11-14T07:35:17Z

function find(source, target) {
    if (!source || source.length == 0) {
        return -1;
    }

    if (!target || target.length == 0) {
        return -1;
    }

    let sourceIndex = 0;
    let targetIndex = 0;

    while (sourceIndex < source.length && targetIndex < target.length) {
        if (source[sourceIndex] == target[targetIndex]) {
            targetIndex++;
        } else {
            targetIndex = 0;
        }

        sourceIndex++;
    }

    return targetIndex < target.length ? -1 : sourceIndex - target.length;
}

89466598946659 · 2024-11-14T07:35:52Z

您的邮件已收到！O(∩_∩)O！--------Pan

yygmind mentioned this issue Jul 14, 2019

前端 100 问：能搞懂80%的请把简历给我 yygmind/blog#43

Open

yygmind added the 编程题 label Dec 16, 2019

dleged mentioned this issue Mar 20, 2020

因为 T 的 length 是一定的，所以在循环S的的时候，循环当前项 i 后面至少还有 T.length 个元素 #360

Closed

第 71 题： 实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。 #119

第 71 题： 实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。 #119

Comments

ZodiacSyndicate commented May 10, 2019

jjeejj commented May 10, 2019 • edited Loading

keiseiTi commented May 10, 2019 • edited Loading

sgzhm4444 commented May 10, 2019

JayZangwill commented May 10, 2019 • edited Loading

Vdan123 commented May 10, 2019

FishPlusOrange commented May 10, 2019 • edited Loading

kingstone3 commented May 10, 2019 • edited Loading

FounderIsShadowWalker commented May 10, 2019

LiuMengzhou commented May 10, 2019 • edited Loading

LiuMengzhou commented May 10, 2019

Tangjj1996 commented May 10, 2019

FishPlusOrange commented May 10, 2019

goodwinfame commented May 10, 2019

cheungkin24 commented May 13, 2019

LiuL0703 commented May 15, 2019

ZhangMingZhao1 commented May 15, 2019 • edited Loading

ckjie commented Jun 24, 2019

dorseysen commented Jun 27, 2019 • edited Loading

dongj0316 commented Jun 27, 2019 • edited Loading

libin1991 commented Jul 9, 2019

xyxiao001 commented Jul 12, 2019

hudie09143672 commented Jul 12, 2019

qiannianchong25 commented Jul 26, 2019

dengshangli commented Jul 29, 2019

ZYSHINee commented Jul 30, 2019 • edited Loading

Stevendwy commented Aug 1, 2019

SpengF commented Aug 2, 2019

montage-f commented Aug 2, 2019

montage-f commented Aug 2, 2019

coveyz commented Jan 6, 2020

shenxuxiang commented Feb 5, 2020

SerinaJingyiLu commented Mar 5, 2020 • edited Loading

dleged commented Mar 20, 2020

litokele2018 commented Mar 25, 2020

coveyz commented Apr 22, 2020

wubing0324 commented May 7, 2020 • edited Loading

snowBoby commented May 31, 2020

jakesamz commented Jun 13, 2020

xueshuai commented Jun 26, 2020

xiaofangnihao commented Jul 17, 2020

89466598946659 commented Aug 23, 2020

Gcalolin commented Aug 27, 2020

orime commented Jan 30, 2021

ghost commented Feb 23, 2021

shuai4983958 commented Mar 3, 2021

xiaocongWang commented Apr 27, 2021

haiyangzhishengs commented Jul 7, 2021

hdsuperman commented Nov 18, 2021

Four-Names commented Feb 24, 2022

yuerdev commented Jun 28, 2022

Lxming1 commented Aug 8, 2022

89466598946659 commented Aug 8, 2022 via email

benzhemin commented Feb 24, 2023

xia0ming commented Apr 7, 2023

89466598946659 commented Apr 7, 2023 via email

yinzuowen commented Nov 14, 2024 • edited Loading

89466598946659 commented Nov 14, 2024 via email

第 71 题：实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。 #119

第 71 题：实现一个字符串匹配算法，从长度为 n 的字符串 S 中，查找是否存在字符串 T，T 的长度是 m，若存在返回所在位置。 #119

jjeejj commented May 10, 2019 •

edited

Loading

keiseiTi commented May 10, 2019 •

edited

Loading

JayZangwill commented May 10, 2019 •

edited

Loading

FishPlusOrange commented May 10, 2019 •

edited

Loading

kingstone3 commented May 10, 2019 •

edited

Loading

LiuMengzhou commented May 10, 2019 •

edited

Loading

ZhangMingZhao1 commented May 15, 2019 •

edited

Loading

dorseysen commented Jun 27, 2019 •

edited

Loading

dongj0316 commented Jun 27, 2019 •

edited

Loading

ZYSHINee commented Jul 30, 2019 •

edited

Loading

SerinaJingyiLu commented Mar 5, 2020 •

edited

Loading

wubing0324 commented May 7, 2020 •

edited

Loading

yinzuowen commented Nov 14, 2024 •

edited

Loading