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

[ZodiacSyndicate]

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]

// 因为 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]

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

[sgzhm4444]

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]

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

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

[Vdan123]

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]

我的核心思想是使用 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]

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]

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

[LiuMengzhou]

用了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]

我的核心思想是使用 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]

我的核心思想是使用 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]

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

[goodwinfame]

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

[cheungkin24]

// 因为 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]

我觉得是考KMP算法吧