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

Question

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
}

Answer 1

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

Answer 2

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

Answer 3

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));

Answer 4

// 因为 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;
};

Answer 5

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

Answer 6

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

这个实现的有问题?

Answer 7

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

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

Answer 8

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

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

这里题目考的是算法实现，不是api运用

Answer 9

/* KMP的优化算法 (寻找匹配字符串的前缀与后缀最大公共长度，该值仅仅与匹配字符串相关)*/

function index(string, searchString) {
  let next = getLongestPS(searchString);
  let i = 0,
      j = 0;
  while (i <= (string.length - 1) && j <= (searchString.length - 1)) {
      if (string[i] === searchString[j]) {
          i++;
          j++;
      } else {
          // 注意当不匹配时,并不移动字符串,而是移动匹配字符串。(回溯)
          if (j == 0) {
            // 当匹配字符串和字符串第一位不匹配时。继续向后移动字符串。
              i++;
          } else {
              j = next[j];
          }
      }
  }
  if (j > searchString.length - 1) {
      return i - searchString.length;
  }
  return -1;
}


/*
* longestPS
* 求一段字符串的前缀与后缀的最大公共长度;
* */
function getLongestPS(searchString) {
  let i = 0;
  let next = [0];
  let j = 1;
  while (j < searchString.length) {
      if (searchString[i] == searchString[j]) {
          next[j] = i + 1;
          i++;
          j++;
      } else {
          if (i == 0) {
              next[j] = 0
              j++;
          } else {
              i = next[i - 1];
          }
      }
  }
  return next;
}

let string = "sdfabasdlfsaslfjslkadadfjlabab";
let searchString = "abab";

console.log(index(string, searchString));
console.log(string.indexOf(searchString));

Answer 10

// 为啥不用，项目开发中难道现成的不用，还写一堆自拟定API？表示无法理解。
function searchIndex(S, T, num = 0) {
  return S.match(new RegExp(T, 'g')).map((_, i) => {
    return (num = S.indexOf(T, num + 1));
  });
}
console.log(searchIndex('Hello World', 'o'));

Answer 11

// 因为 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;
};

There will be bugs if S===T

Answer 12

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
}

这样是不是更简单一些呀

const find = (str, t)=> Array.from(str).findIndex((value)=> value === t)  

Answer 13

这题考的是 KMP 算法：

名词

• 主串 （文本串）
• 子串 （模式串）

概念

相比于傻瓜式的字符串匹配，即在遍历主子串时，一旦出现对应位置的字符不匹配，主子串都要回溯后再重新遍历匹配。

其实已匹配过的字符，再去回溯匹配是多余，因为前面的字符已经一一匹配对应了，你再右移后就错位了，肯定不会匹配。

KMP 算法就是为了避免主串回溯，子串右移已匹配的最大位数，来避免明知道不会匹配的无效移位。

原理

• 给定模式串时，模式串自身的部分匹配数就已知了。也就是最大的前缀和后缀长度。初始化这个位置后，我们就知道当遍历到模式串的一个字符发现与主串不匹配时，直接右移到前缀和后缀一致的位置，也就是公式：

右移数 = 已匹配数 - 最大的部分匹配数

• 在遍历时，主串不必回溯，主串的回溯是多余的，遍历过一次后就已知与子串是否匹配了。

Answer 14

@jjeejj S.length - T.length 无法获取 T处于 S 最后处这种情况，应该改为 S.length - T.length + 1

Answer 15

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'));

Answer 16

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

Answer 17

首先是用了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")) 

结果在这里哈：

欢迎指正！！

Answer 18

// 因为 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 少了

Answer 19

我的核心思想是使用 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，仅返回第一个的位置

Answer 20

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;
}

Answer 21

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

Answer 22

用了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;
  }

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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

Answer 28

我觉得是考KMP算法吧

Answer 29

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 ）

Answer 30

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;
}

Answer 31

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

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

Answer 32

搜索了一下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;
}

Answer 33

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)

Answer 34

Answer 35

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

Answer 36

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中重复出现的，需要将两个位置都展示出来？

Answer 37

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

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

Answer 38

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);

Answer 39

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

Answer 40

// 因为 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;
};