关于程序员:字符串匹配算法BFKMP

55次阅读

共计 2578 个字符,预计需要花费 7 分钟才能阅读完成。

一、应用串的基本操作函数

Index(S,T,pos) 定位操作。若主串 S 中存在与串 T 值雷同的字串,则返回它在主串 S 中第 pos 个字符之后第一次呈现的地位;否则函数值为 0

在 Java 中,对应函数为 S.indexOf(String T)

二、BF 模式匹配算法

别离用 i 和 j 示意主串 S 和字串 T 中以后正在比拟的字符地位。算法思维为:从主串 S 的第 pos 个字符起,与模式串的第一个字符进行比拟,若相等,则持续一一比拟后续字符;否则从主串的下一个字符起再从新和模式串的字符比拟。依此类推,直至模式串 T 中的每个字符顺次和主串 S 中的一个间断的字符序列相等,则称匹配胜利,函数返回值为和模式串 T 中的第一个字符相等的字符在主串 S 中的序号,否则成匹配不胜利,函数返回值为 0。

在匹配胜利的状况下,思考以下两种极其状况。其中 m 为主串长度,n 为模式串长度。

(1)最好状况下,每趟不胜利的匹配都产生在模式串的第一个字符与主串中相应字符的比拟。此时的工夫复杂度为 O(m+n) 例如:S="aaaaaaaba" T="ba"

(2)最坏状况下,每趟不胜利的匹配都产生在模式串的最初一个字符与主串中相应字符的比拟。此时的工夫复杂度为 O(m*n) 例如:S="aaaaaaab" T="aab"

图 1 展现了模式串 T=“abcac” 和主串的匹配过程(pos=1)

BF 算法思路简略。但当匹配失败时,主串的指针 i 总是回溯到 i -j+ 1 地位,模式串的指针 j 总是复原到首字符地位 j =1。因而,算法工夫复杂度高。

三、KMP 算法

(以下剖析元素下标皆从 1 开始)

改良点:失配时,不需回溯 i 指针,而是利用曾经比拟过的信息,仅将模式串向右挪动到一个适合的地位,并从这个地位开始和主串进行比拟,这个适合的地位仅与字串自身的构造无关,而与主串无关。KMP 算法的工夫复杂度为 O(m+n)。

回顾图 1 的匹配过程,在第三趟匹配中,i=7、j= 5 时失配,于是又从 i =4、j= 1 处从新开始比拟。然而,i= 4 和 j =1、i= 5 和 j =1、i= 6 和 j = 1 这三次比拟都是不用进行的,因为从第三趟匹配的后果可知,主串中第 4、5、6 个字符是’b’,’c’,’a’,而字串中的第一个字符是‘a‘,因而它无须再和这三个字符进行比拟,仅需将子串向右滑动 3 个字符的地位持续进行 i =7、j= 2 时的字符比拟即可。

关键在于明确的晓得每个时刻须要挪动的间隔。在此之前,引入三个概念:前缀、后缀和局部匹配值

  • 前缀:除最初一个字符以外,字符串的所有头部字串。
  • 后缀:除第一个字符以外,字符串的所有尾部字串。
  • 局部匹配值:前缀和后缀的最大公共元素长度。

上面以“ABCDABD”为例来了解这三个概念:

局部匹配值的作用:

挪动位数 = 已匹配胜利的字符数 - 失配字符的上一个字符所对应的局部匹配值 即:move=(j-1)-next[j-1]

根据上述办法失去模式串“abcac”的局部匹配值为00010。写成数组的模式,就失去了 next 数组:

字符 a b c a c
next 0 0 0 1 0

批改 next 数组:

字符 a b c a c
next 0 0 0 1 0
右移 1 位 -1 0 0 0 1

咱们留神到:

  1. 第一个元素右移后空进去的地位填入了 -1。这是因为当第一个字符就不匹配时,只能往后挪动一位
  2. 最初一个元素在右移中溢出。因为原来的模式串中,最初一个元素的局部匹配值是其下一个元素应用的,但显然没有下一个元素,故能够舍去。(这里如果不舍去,将会有额定的作用,例如求循环节。)

这样,上式就被改写成 move=(j-1)-next[j](如果下标从 0 开始,则是 move=j-next[j])

即:挪动位数 = 已匹配胜利的字符数 - 失配字符所对应的局部匹配值

失配后与 i 从新对应的 j 的地位:j=j-move=j-((j-1)-next[j])=next[j]+1(如果下标从 0 开始,则是 j =j-move=j-(j-next[j]) = next[j])

对人而言,用上述办法很容易求 next 数组,但对于计算机来说,能够用一种更加高效的办法来求:

设 T 位子串,当 next[j]曾经求得,next[j+1]的值能够分两种状况剖析。

  1. 若子串中字符 $t_j$ 等于 $t_i$,显然 next[i+1]=j+1,因为 j 位以后 T 最长相等前后缀长度。
  2. 若 $t_j$ 不等于 $t_i$,将 $t_{i-j+1}$…$t_i$ 当作主串,将 $t_1$…$t_j$ 当作子串。相似于失配问题,需挪动子串,即令 j =next[j],持续进行比拟,若满足(1),则求得 next[j+1]。

KMP 算法仅 在主串与子串有很多“局部匹配”时才显得更高效,其次要长处是主串不回溯

代码

import java.util.Scanner;
// // 下标从 0 开始,只找第一个呈现的匹配后果
public
class KMP
{
static int sLen;
static int pLen;
static char[] S = new char[1000009];
static char[] P = new char[10009];
static int[] next = new int[10009];
static void GetNext()
{next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{if (k == -1 || P[j] == P[k])
{
k++;
j++;
next[j] = k;
}
else
{k = next[k];
}
}
}
static int KMP()
{
int i = 0;
int j = 0;
while (i < sLen && j < pLen)
{if (j == -1 || S[i] == P[j])
{
i++;
j++;
}
else
{j = next[j];
}
}
if (j == pLen)
return i - j + 1; // 下标是从 0 开始的
else
return -1;
}
public
static void main(String[] args)
{Scanner scan = new Scanner(System.in);
System.out.print("请输出主串:");
String s1 = scan.nextLine();
sLen = s1.length();
S = s1.toCharArray();
System.out.print("请输出子串:");
String s2 = scan.nextLine();
pLen = s2.length();
P = s2.toCharArray();
GetNext();
System.out.println(KMP());
}
}

正文完
 0