字符串查找(kmp)

Posted1 by 呼延十 on September 15, 2018 Hot:

1.字符串查找(kmp)

来源:

lintcode-字符串查找
lintcode-字符串查找II

问题描述

描述

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1。

说明

在面试中我是否需要实现KMP算法?

不需要,当这种问题出现在面试中时,面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。

样例

如果 source = “source” 和 target = “target”,返回 -1。

如果 source = “abcdabcdefg” 和 target = “bcd”,返回 1。

挑战

O(n2)的算法是可以接受的。如果你能用O(n)的算法做出来那更加好。(提示:KMP)

解决思路

题目说明中提示了此题的目的为考察KMP算法,但是并不要求强行实现,那么本文将作出两种实验方式,即O(N)和O(N2)两种方法,另外,在文后会有自己对KMP算法的一些理解。

1.暴躁(cao)老哥型方法

当然就是穷举了,假设两个字符串为

ACBACDBB ------T串
ACD   -------p串

那么我们可以首先比较T[0]和P[0],如果相等则比较T[1]和P[1],如果一直到p串结束都相等则返回,中间如果有不相等,则比较T[1]和P[0]…..

即:逐个比较,当发生不相等时,将T串的开始比较位置向后移动一位,再次逐个比较,直到拿到结果。

这种方法胜在简单粗暴,虽然浪费了点但是能在短时间内理解并实现。

2.机制boy型方法(KMP算法)。

在上面的例子中,当第一次发现AC相同但是B/D不同时,再见将T[1]和P[0]相比较,是一个浪费的行为,因为因为很明显:前面的2位都与自身的前两位一样,而自身的前两位并无相等,可以推出T[1]和P[0]肯定不相等。

这就得出KMP的基本思想:将之前一次的比较信息(如前面的AC两位相等)不要抛弃,而是从这个信息中获取我们应该跳过一些“必不可能”匹配的值,以此来提高性能。

重新举例:

BBC ABCDAB ABCDABCDABDE     -------T串
ABCDABD     -------P串

在这个例子中,
1.第一次比较:T[0] != P[0],向后移一位; 2.第二次比较:T[1] != P[0], 向后移一位; .. 3.直到:T[4] = P[0],都向后移动一位; 4.T[5] = P[1],再次都想后移动一位。 …

BBC ABCDAB ABCDABCDABDE     -------T串
    ABCDABD     -------P串

5.直到:T[10] != P[6],这个时候返回第三部,重新从T[5]和P[0]开始比较吗?no!!此时肉眼可见,机智的方法是将字符串这样比较:

BBC ABCDAB ABCDABCDABDE     -------T串
        ABCDABD     -------P串

即直接比较T[10]和P[2] 空格与C,为什么呢?因为此时前面的2位AB我们是可以知道他们相等的,怎么知道的呢?

注意在 4 步骤后的示例中,P串的前6位已经完全匹配了,想知道在T中刚比较过的有几位与P串开头相同,只需要比较已经匹配的6位中,前缀和后缀相同有几位就好。
在此例中:前6位为ABCDAB,明显是2位相同(前缀AB和后缀AB),那么只需要将T[10]与P[2]相比较就好。

6.T[10] != P[2],此时前面两位为AB,前缀与后缀并无相同,所以将T[10]与P[0]进行相比。

7.T[10] != P[0],比较 P[11] 和P[0],进入下一个循环。

8.由于匹配可能在P串的任何一个地方“断裂”,那么每次断裂,都需要算一次“前缀后缀相同的长度”,也是极其浪费的行为,因此,在KMP算法开始前,会对P串进行一次计算,得到在每个位置发生“断裂”时,P串指针回溯的位置,即当前已匹配字段的前缀后缀相同长度。也就是众多KMP算法讲解中的next数组。

总结:原始的暴力方法,当发现不相同后,将T串的指针回溯,这样及其浪费,而在KMP中,避免了T串的指针回溯,在发现不相等时,通过对已匹配字段的分析,将P串指针回溯一个适合的值,而T串指针只有在首字母就不相同时才会继续前进。

写完这一段,深感自己写的糊里糊涂,但是已尽到目前的能力,后续如果有能力,可以再出一个插图版的讲解。 在这里介绍两个我在学习过程中,看到的关于KMP的博客,属于个人认为讲解的较为清晰的,分享给大家,一起进步。 简洁,说明原理型 详细,逻辑鬼才型

个人推荐:先读简洁篇,对原理有个大概的了解,然后去细读详细篇,否则可能会出现完全看不懂的情况。当然,如果你看我的博客就已经懂了(怎么可能!!),烦请一定留言告诉我,鼓励下我!!

实现代码

暴躁老哥版本(O(N2))

public int stringIndex(String source, String target) {
  int i = 0, j = 0;
  int sLen = source.length(), pLen = target.length();
  char[] src = source.toCharArray();
  char[] ptn = target.toCharArray();
  while (i < sLen && j < pLen) {
    if (src[i] == ptn[j]) {
      // 如果当前字符匹配成功,则将两者各自增1,继续比较后面的字符
      i++;
      j++;
    } else {
      // 如果当前字符匹配不成功,则i回溯到此次匹配最开始的位置+1处,也就是i = i - j + 1
      // (因为i,j是同步增长的), j = 0;
      i = i - j + 1;
      j = 0;
    }
  }
  // 匹配成功,则返回模式字符串在原字符串中首次出现的位置;否则返回-1
  if (j == pLen) {
    return i - j;
  } else {
    return -1;
  }
}

机制boy型(O(N))

//计算返回值
public int stringIndex(String source, String target) {
  //多检测下极端值总是没有坏处的.尤其是面试和刷题.
  if (target == null) {
    return -1;
  }
  int pLen = target.length();
  if (pLen == 0 && source != null) {
    return 0;
  }

  if (source == null) {
    return -1;
  }
  int sLen = source.length();
  if (sLen == 0) {
    return -1;
  }

  int i = 0, j = 0;
  char[] src = source.toCharArray();
  char[] ptn = target.toCharArray();
  int[] next = getNext(ptn);
  while (i < sLen && j < pLen) {
    // 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
    if (j == -1 || src[i] == ptn[j]) {
      i++;
      j++;
    } else {
      // 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
      j = next[j];
    }
  }
  if (j == pLen) {
    return i - j;
  }
  return -1;

}
//获取next数组
private int[] getNext(char[] p) {
  // 已知next[j] = k,利用递归的思想求出next[j+1]的值
  // 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
  // 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
  // 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
  // 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
  int pLen = p.length;
  int[] next = new int[pLen];
  int k = -1;
  int j = 0;
  next[0] = -1; // next数组中next[0]为-1
  while (j < pLen - 1) {
    if (k == -1 || p[j] == p[k]) {
      k++;
      j++;
      next[j] = k;
    } else {
      k = next[k];
    }
  }
  return next;
}

后记

单就字符串查找这个算法而言,网上思路繁多,而且自己多想一下总有具有自己特色的实现方法。

KMP算是一个比较通用且效率较为不错(非最优)的实现方法,思路较为一致:找出一个当匹配失败时子串回溯的长度。然而在具体实现过程中,尤其是next数组的求解过程中,我看到了许多思路且都很难快速理解。

恕在下愚钝,理解了老半天还是模模糊糊的,万一哪天豁然开朗,再来重新补充一份简单易懂的讲解。

完。




ChangeLog

2018-09-15 添加思路及KMP讲解
2018-09-16 添加实现代码

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十