定义txt为文本串（长串），pat为模式串（短串）。查找子串的方法就是在文本串txt中查找模式串pat第一次出现的位置。

  1. function search(pat, txt) {
  2.   const M = pat.length;
  3.   const N = txt.length;
  4.   for (let i = 0; i <= N - M; i += 1) {
  5.     let j;
  6.     for (j = 0; j < M; j += 1) {
  7.       if (txt.charAt(i + j) !== pat.charAt(j)) break;
  8.     }
  9.     if (j === M) return i; // 找到匹配
  10.   }
  11.   return -1; // 未找到匹配
  12. }

指针i指向文本串匹配的起始位置，指针j指向模式串匹配的位置。对于每个i，代码首先将j重置为0并不断将它增大，直到找到了一个不匹配的字符或者模式结束为止。如果模式串结束之前文本串就已经结束了(i === N - M + 1)，那么就是没有找到匹配的模式串，返回-1。

另一种实现是基于回退的思想。指针i指向文本串匹配的位置，指针j指向模式串匹配的位置。如果i和j指向的字符匹配，都位移一步；如果i和j指向的字符不匹配，那么需要回退两个指针的值：将i指向本次匹配的开始位置的下一个字符（i = i - j + 1），将j重新执行模式串的开头（j = 0）。代码如下

  1. function search(pat, txt) {
  2.   const M = pat.length;
  3.   const N = txt.length;
  4.   let i, j;
  5.   for (i = 0, j = 0; i < N && j < M; i += 1) {
  6.     if (txt.charAt(i) === pat.charAt(j)) {
  7.       j += 1;
  8.     } else {
  9.       // i和j指向的字符不匹配，需要回退这两个指针的值，
  10.       // 将j重新指向模式的开头，将i执行本次匹配的开始位置的下一个字符
  11.       i -= j;
  12.       j = 0;
  13.     }
  14.   }
  15.   if (j === M) return i - M; // 找到匹配
  16.   return -1; // 未找到匹配
  17. }

两种思路复杂度都一样的，时间复杂度O(MN)，空间复杂度O(1)

不足

此算法是十分笨的，每次遇到不相等时，就要回退从头开始逐个比较。那么能否利用已匹配部分的文本信息避免将指针会退到这些已知的字符之前？

参考资料

  1. 《算法》5.3.2 暴力子字符串查找算法