回文子串对(扩展kmp-kmp与回文子串)

Problem 1 回文子串对(manacher.cpp/c/pas)

【题目描述】

给定一长度为n的小写字母串,求有多少对回文子串,它们的交集非空。

一对回文子串的交集非空:[a,b]、[c,d](a≠c或b≠d)为2个回文子串,且[a,b]∩[c,d]≠∅。

【输入格式】

第一行一个整数n表示串长。

第二行长度为n的小写字母串。

【输出格式】

输出一个整数表示答案,答案对1000000007取模。

【样例输入】

4

babb

【样例输出】

6

【数据范围】

对于30%的数据,n<=1000

另有10%的数据,串里仅含一种字母。

对于100%的数据,n<=2*10^6

 

找到最前面的max(r[j]+j),映射过去

设r[i]表示以i点为中心点的最长回文子串

则如图:



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define F (1000000007)
#define MAXN (2000000+10)
using namespace std;
long long r[MAXN],n,L[MAXN][2],R[MAXN][3];
char s[MAXN];
int main()
{
	freopen("manacher.in","r",stdin);
	freopen("manacher.out","w",stdout);
	scanf("%d%s",&n,s+1);
	memset(r,0,sizeof(r));
	memset(L,0,sizeof(L));
	memset(R,0,sizeof(R));
	int j=0;
	for (int i=1;i<=n;i++)
	{
		if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);
		while (i-r[i]>1&&i+r[i]<n&&s[i-r[i]-1]==s[i+r[i]+1]) r[i]++;
		if (r[i]+i>r[j]+j) j=i;
		L[i-r[i]][0]+=1;
		L[i+1][0]-=1;
		R[i][0]++;
		R[i+r[i]+1][0]--;
	}
//	for (int i=1;i<=n;i++) cout<<r[i]<<' ';cout<<endl;
	j=0;memset(r,0,sizeof(r));
	for (int i=1;i<n;i++)
	{
		if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);
		while (i-r[i]>0&&i+r[i]<=n&&s[i+1-r[i]-1]==s[i+r[i]+1]) r[i]++;
		if (r[i]+i>r[j]+j) j=i;
		L[i+1-r[i]][0]+=1;
		L[i+1][0]-=1;
		R[i+1][0]++;
		R[i+r[i]+1][0]--;
	}
/*
	for (int i=1;i<=n;i++) cout<<L[i][0]<<' ';cout<<endl;
	for (int i=1;i<=n;i++) cout<<R[i][0]<<' ';cout<<endl;
*/
	for (int i=1;i<=n;i++) L[i][1]=L[i][0]+L[i-1][1];
	for (int j=1;j<=2;j++)
		for (int i=1;i<=n;i++)
			R[i][j]=R[i-1][j]+R[i][j-1];
	long long ans=0;
	for (int i=1;i<=n;i++)
		ans=(ans+L[i][1]*R[i-1][2])%F;
	long long tot=0;
	if (R[n][2]%2) tot=(((R[n][2]-1)/2)%F)*((R[n][2])%F)%F;
	else tot=(((R[n][2])/2)%F)*((R[n][2]-1)%F)%F;
//	cout<<tot<<' '<<ans<<endl;

	cout<<((tot-ans+F)%F)<<endl;
	return 0;
}




POJ 1226(最长公共子串含逆序)

Language:
Substrings
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 9639   Accepted: 3319

Description

请找出一些串的最长‘正/逆‘子串,使它为所有的串的子串(即使是逆序也认为包含).

Input

第一行为数据数t,(1 <= t <= 10),
对每组数据而言:第一行为字符串个数 n (1 <= n <= 100),接下来n行为字符串(长度不超过100) .

Output

每行一个数,表示最长'正/逆‘子串的长度。

Sample Input

2
3
ABCD
BCDFF
BRCD
2
rose
orchid

Sample Output

2
2 

Source

还是KMP,先在第一个串中枚举串,之后考察它是否是其它串的'正/逆'子串。


Program P1226;
const
   maxn=100;
   maxt=10;
var
   tt,n,m,i,j,k,ans:longint;
   flag:boolean;
   a:array[1..maxn] of string;
   p:string;
   next:array[1..maxn] of longint;

function kmp(a,b:string):boolean;
var
   i,j,n,m:longint;
begin
   i:=1;j:=0;next[1]:=0;
   n:=length(a); m:=length(b);
   while (i<m) do
   begin
      if (j=0) or (b[i]=b[j]) then
      begin
         inc(i);inc(j);
         if (b[i]<>b[j]) then next[i]:=j else next[i]:=next[j];
      end else j:=next[j];
   end;

   i:=0;j:=0;
   while (i<=n) and (j<=m) do
   begin
      if (j=0) or (a[i]=b[j]) then
      begin
         inc(i);inc(j);
      end else j:=next[j];
   end;
   if (j>m) then exit(true);
   exit(false);
end;
function ob_s(a:string):string;
var
   i,j,n:longint;
begin

   ob_s:=''; n:=length(a);
   for i:=n downto 1 do ob_s:=ob_s+a[i];
end;
function compare(a,b:string):boolean;
var
   n,m:longint;
begin
   n:=length(a);m:=length(b);
   if (n<>m) then exit(n<m);
   for i:=1 to n do
      if a[i]<>b[i] then exit(a[i]<b[i]);
   exit(false);
end;


begin
   readln(tt);
   while (tt>0) do
   begin
      ans:=0;
      readln(n);
      for i:=1 to n do readln(a[i]);

      for i:=1 to length(a[1]) do
         for j:=i to length(a[1]) do
         begin
            p:=copy(a[1],i,j-i+1);
            flag:=true;
            for k:=2 to n do
            begin
               if not((kmp(a[k],p) or kmp(a[k],ob_s(p)))) then
               begin
                  flag:=false; break;
               end;
            end;
            if flag and (length(p)>ans) then ans:=length(p);


         end;

      writeln(ans);
      dec(tt);
   end;
end.


POJ 2185(最大平铺矩阵)

Language:
Milking Grid
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 4346   Accepted: 1780

Description

给定R(1 <= R <= 10,000) *C (1 <= C <= 75) 的矩阵,求它的最大平铺矩阵,不够的地方可部分平铺,但不可重叠。

Input

第一行:R和C.
第2-R+1行每行C个大写字母,表示矩阵.

Output

最大的平铺矩阵面积

Sample Input

2 5
ABABA
ABABA

Sample Output

2

Hint

The entire milking grid can be constructed from repetitions of the pattern 'AB'.

Source

显然这个矩阵必然从左上角开始

由于C比较少,先找出每列最大的平铺线段(行行不影响)

再考虑每行共有且最小的重复部分(可以证明增加重复部分对行的大小无影响)

在考虑行R≤10000,必须用Kmp,不凡假设句末有若干'????'

则对于字符串的P

AEICCCAEICCCAEI C  C  ?   ?   ?  ...

000000123456789 10 11 12  13  14 ...

显然?后的P递增+1,又因答案为Max(i-p[i])(i≥n)

所以(n-p[n])=Max(i-p[i])


Program grid;
const
   maxn=10000;
   maxm=75;
var
   n,m,i,j,k:longint;
   a:array[1..maxn] of string;
   f:array[1..maxm] of longint;
   flag:boolean;
   p:array[1..maxn] of longint;
begin
   fillchar(f,sizeof(f),0);
   readln(n,m);
   for i:=1 to n do
   begin
      readln(a[i]);
      for j:=1 to m do
      begin
         flag:=true;
         for k:=j+1 to m do
            if a[i][k]<>a[i][k-j] then begin flag:=false; break; end;
            if flag then inc(f[j]);
      end;
   end;
   for i:=1 to m do if f[i]=n then break;
   m:=i;

   for i:=1 to n do delete(a[i],m+1,maxlongint);

   j:=0;p[1]:=0;
   for i:=2 to n do
   begin
      while (j>0) and (a[i]<>a[j+1]) do j:=p[j];
      if (a[i]=a[j+1]) then inc(j);
      p[i]:=j;
   end;

   n:=n-p[n];
   writeln(m*n);





end.







POJ 3461(模式匹配数&覆盖函数)

Language:
Oulipo
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 14051   Accepted: 5667

Description

给出两个字符串W和T,求T中有几个W子串。

Input

第一行为数据数.

每组数据有两行W和T,表示模式串和原始串.

Output

对每组数据,每行一个数,表示匹配数.

Sample Input

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

Sample Output

1
3
0

Source


这题用到了KMP中的覆盖函数——P

P和Next的区别是P是指包括当前点的最长覆盖长度,Next是指匹配到i,若不满足条件,将其挪到Next[i],(P[i]<>P[next[i]],P表模式串)

证明:



之后进行查找,若查到(j=m),则j=P[j](为了下一次查找)


Program Poj3461;
const
   maxm=10000;
   maxn=1000000;
var
   tt,n,m,i,j:longint;
   a,b:ansistring;
   P:array[1..maxn] of longint;
function kmp:longint;
var
   n,m,i,j:longint;
begin
   kmp:=0;

   n:=length(a);m:=length(b);
   P[1]:=0;j:=0;
   for i:=2 to m do
   begin
      while (j>0) and (b[j+1]<>b[i]) do j:=p[j];
      if (b[j+1]=b[i]) then inc(j);
      p[i]:=j;
   end;

   j:=0;
   for i:=1 to n do
   begin
      while (j>0) and (b[j+1]<>a[i]) do j:=p[j];
      if (b[j+1]=a[i]) then inc(j);
      if j=m then
      begin
         inc(kmp);
         j:=p[j];
      end;

   end;


end;
begin
   readln(tt);
   while (tt>0) do
   begin
     readln(b);
     readln(a);

     writeln(kmp);

     dec(tt);
   end;

end.



POJ 1961(KMP前缀最长重复子串)

Language:
Period
Time Limit: 3000MS   Memory Limit: 30000K
Total Submissions: 10179   Accepted: 4662

Description

求一个字符串中,所有循环节大于2的子串。

Input

有若干组数据,
每组数据第一行为字符串长度,第二行为字符串
以0结束。

Output

对于每组数据,输出'Test case #i",i从0开始,之后每行输出两个数,分别表示前缀长度和循环节数(>1).
每组数据后输出一个空行。

Sample Input

3
aaa
12
aabaabaabaab
0

Sample Output

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

Source

这题就是KMP问题。

还是Next,

先做不判重复优化的处理

观察发现若前面有循环节,则有i->i-p->i-2p...->i-kp=1

则i-next[i]表示循环结长度p,显然有p|(i-1),(i-1) div p>1.

如下:



Program Poj1961;
const
   maxn=10000000;
var
   i,j,tt,n,duan_luo:longint;
   next:array[1..maxn] of longint;
   a:ansistring;
begin
   tt:=1;
   while (true) do
   begin
      readln(n);
      if n=0 then break;
      readln(a);  inc(n); a:=a+'.';
      i:=1;j:=0;next[1]:=0;
      while (i<=n-1) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
             inc(i);inc(j);
           //  if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
             next[i]:=j;
         end
         else j:=next[j];
      end;

      writeln('Test case #',tt);

      for i:=2 to n do
      begin
         duan_luo:=i-next[i];
         if (duan_luo>0) and ((i-1) mod duan_luo=0) and ((i-1) div duan_luo>1) then
            writeln(i-1,' ',(i-1) div duan_luo);



      end;

//    readln;
      writeln;
      inc(tt);
   end;

end.


POJ 3080(最长公共子串)

Language:
Blue Jeans
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8767   Accepted: 3688

Description

给出若干个基因串(由'A','T','S','C'构成),请找出最长公共子串。

Input

第一行为数据数。
对每组数据:第一行为字符串的个数m(2 <= m <= 10)
                        之后m行,每行一个基因串(有且仅有60个字母)

Output

对每组数据,找出最长公共子串,如果长度小于3,请输出 "no significant commonalities" ,否则输出最长的字符串,若有多个答案,输出字典序最小的。

Sample Input

3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Sample Output

no significant commonalities
AGATAC
CATCATCAT

Source

枚举字符串更新答案,用kmp算法进行匹配。


Program BlueJeans;
const
   maxn=60;
   maxm=10;
var
   tt,i,j,k,n,m:longint;
   a:array[1..maxm] of string;
   next:array[1..maxn] of longint;
   p,ans:string;
   flag:boolean;

function kmp(a,s:string):boolean;
var
   i,j,n:longint;
begin
   n:=length(a);

   j:=0; next[1]:=0; i:=1;
   while i<n do
   begin
      if (j=0) or (a[i]=a[j]) then
      begin
         inc(i); inc(j);
         if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
      end else j:=next[j];
   end;

   j:=0; i:=0;
   while (i<=maxn) and (j<=n) do
   begin
      if (j=0) or (a[j]=s[i]) then
      begin
         inc(i); inc(j);
  //       if (j=n) then exit(true);
      end else j:=next[j];
   end;

   if j>n then exit(true);
   exit(false);


end;
function compare(a,b:string):boolean;
var
   i,n,m:longint;
begin
   n:=length(a); m:=length(b);
   if (n<>m) then exit(n<m);
   for i:=1 to n do if (a[i]<>b[i]) then exit(ord(a[i])>ord(b[i]));
   exit(false);
end;
begin
   readln(tt);
   while (tt>0) do
   begin
      ans:='';
      readln(m);
      for i:=1 to m do readln(a[i]);

      for i:=1 to maxn do
         for j:=i to maxn do
         begin
            p:=copy(a[1],i,j-i+1);
            flag:=false;
            for k:=2 to m do
            begin
               if not(kmp(p,a[k])) then begin flag:=true; break; end;
            end;
            if not(flag) and (compare(ans,p)) then ans:=p;
         end;

      if length(ans)<3 then writeln('no significant commonalities')
      else writeln(ans);




      dec(tt);
   end;
end.

POJ 2752(不满足P[i]<>P[next[i]] 的next函数)

Language:
Seek the Name, Seek the Fame
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 8682   Accepted: 4112

Description

给定一个字符串P,求它所有的满足P[1..i]到P[n-i+1..n]的i.

Input

数据有若干行
每行为一组数据P,1 <= Length of P <= 400000. 

Output

每行一组数据,按数字升序输出所有的i. 

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5

Source


要考虑KMP中Next函数的性质-P[next[i]]<>P[i]

如果这个条件不满足呢?

先在字符串后插入一个'.',表示'.'前的循环,这样就能规避这一点(因为‘.’不会与任何字母重合)

再把后面那个if从句删掉(它只能跳过一些-非全部的-P[next[i]]<>P[i]的情况,因为.后面可能出现两次'a'

这样就可以了,最后把答案(由于不考虑a[i],只考虑前面循环节的长度,故-1)


Program SeekName;
const
    maxn=400000;
var
   n,i,j,size:longint;
   a:ansistring;
   ans,next:array[1..maxn] of longint;

begin
   while not seekeof do
   begin
      readln(a); a:=a+'.';
      n:=length(a);
      j:=0;next[1]:=0;i:=1;
      while (i<n) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
            inc(i);
            inc(j);
         //   if (a[i]<>a[j]) then next[i]:=j else next[i]:=next[j];
            next[i]:=j;
         end else j:=next[j];
      end;
      size:=0; j:=n;
      repeat
         inc(size);
         ans[size]:=j-1;
         j:=next[j];
      until j<=1;


      write(ans[size]);
      for i:=size-1 downto 1 do write(' ',ans[i]);
      writeln;



   end;

end.


POJ 2406(KMP中next的性质)

Power Strings
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 24403   Accepted: 10264

Description

给你一个字符串a,问a最多由几个完全相同的子串连接而成

Input

每一个测试点都会给你一个长度为m(1<=m<=1000000)的字符串,并以句号结尾。

Output

输出a最多由几个完全相同的子串连接而成。

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint

用cin会T

Source

这题要用到KMP算法中next的性质……我研究了一上午才搞懂

一个字母的next表示这个字母要向后跳到哪一位才能与原字符串匹配

a b c a  b  c

0 0 0 1  2  3

释义:第2个a=1->若不匹配可跳到第一个字符为起点(0表示完全不匹配)

经过观察发现

abcabcabc

000123456

a a i a a i a a i

0 10 1 2 3 4 5 6

 于是发现next函数的嵌套关系:

L1-L2

L1-L2 L3-L4

于是如果一个字符串是循环的,那么最后的next正好就应该指向循环的那个圈

即便本身有自带的链也满足,观察下图即可当证明了:

Program PowerString;
const
   maxn=10000010;
var
   n,i,j,duan_luo:longint;
   next:array[0..maxn] of longint;
   a,b:ansistring;
function check:boolean;
var
   i,j:longint;
begin
   if (n mod duan_luo>0) then exit(false);
   for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
   exit(true);


end;
begin
   while not eof do
   begin
      readln(a);
      if a='.' then break;

      n:=length(a);
      j:=0; i:=1; next[1]:=0;
      while (i<n) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
            inc(i);inc(j);
            if (a[i]<>a[j]) then next[i]:=next[j]
            else next[i]:=j;
         end
         else j:=next[j];

      end;

      duan_luo:=n-next[i];
      if check then writeln(n div duan_luo) else writeln(1);





   end;
end.

代码2(前面的next总觉得有问题,于是我自行修改):

Program PowerString;
const
   maxn=10000010;
var
   n,i,j,duan_luo:longint;
   next:array[0..maxn] of longint;
   a,b:ansistring;
function check:boolean;
var
   i,j:longint;
begin
   if (n mod duan_luo>0) then exit(false);
   for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
   exit(true);


end;
begin
   while not eof do
   begin
      readln(a);
      if a='.' then break;

      n:=length(a);
      j:=0; i:=1; next[1]:=0;
      while (i<n) do
      begin
         if (j=0) or (a[i]=a[j]) then
         begin
            inc(i);inc(j);
        //    if (a[i]<>a[j]) then next[i]:=next[j]
            while (j>0) and (a[i]<>a[j]) do j:=next[j];
             next[i]:=j;
         end
         else j:=next[j];

      end;

      duan_luo:=n-next[i];
      if check then writeln(n div duan_luo) else writeln(1);





   end;
end.

代码3:(最后那个if好像就用不着了……):

Program PowerString;
const
   maxn=10000010;
var
   n,i,j,duan_luo:longint;
   next:array[0..maxn] of longint;
   a,b:ansistring;
function check:boolean;
var
   i,j:longint;
begin
   if (n mod duan_luo>0) then exit(false);
   for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
   exit(true);


end;
begin
   while not eof do
   begin
      readln(a);
      if a='.' then break;

      n:=length(a);
      j:=0; i:=1; next[1]:=0;
      while (i<n) do
      begin
         inc(i);inc(j);
       //if (a[i]<>a[j]) then next[i]:=next[j]
         while (j>0) and (a[i]<>a[j]) do j:=next[j];
         next[i]:=j;

      end;

      duan_luo:=n-next[i];
      if check then writeln(n div duan_luo) else writeln(1);





   end;
end.

代码4:这层while有有只递增i,感觉没必要:

Program PowerString;
const
   maxn=10000010;
var
   n,i,j,duan_luo:longint;
   next:array[0..maxn] of longint;
   a,b:ansistring;
function check:boolean;
var
   i,j:longint;
begin
   if (n mod duan_luo>0) then exit(false);
   for i:=duan_luo+1 to n do if (a[i]<>a[i-duan_luo]) then exit(false);
   exit(true);


end;
begin
   while not eof do
   begin
      readln(a);
      if a='.' then break;

      n:=length(a);
      j:=0; i:=1; next[1]:=0;
      for i:=2 to n do
      begin
         inc(j);
       //if (a[i]<>a[j]) then next[i]:=next[j]
         while (j>0) and (a[i]<>a[j]) do j:=next[j];
         next[i]:=j;
      end;

      duan_luo:=n-next[i];
      if check then writeln(n div duan_luo) else writeln(1);





   end;
end.

KMP

作者:July。
出处:http://blog.csdn.net/v_JULY_v/

引记

    此前一天,一位MS的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B树、后缀树,包括KMP算法,唯独在讲解KMP算法的时候,言语磕磕碰碰,我想,原因有二:1、博客内的东西不常回顾,忘了不少;2、便是我对KMP算法的理解还不够彻底,自不用说讲解自如,运用自如了。所以,特再写本篇文章。由于此前,个人已经写过关于KMP算法的两篇文章,所以,本文名为:KMP算法之总结篇。

   本文分为如下六个部分:

  1. 第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度,并两相对照各自的匹配原理;
  2. 第二部分、通过我此前第二篇文章的引用,用图从头到尾详细阐述KMP算法中的next数组求法,并运用求得的next数组写出KMP算法的源码;
  3. 第三部分、KMP算法的两种实现,代码实现一是根据本人关于KMP算法的第二篇文章所写,代码实现二是根据本人的关于KMP算法的第一篇文章所写;
  4. 第四部分、测试,分别对第三部分的两种实现中next数组的求法进行测试,挖掘其区别之所在;
  5. 第五部分、KMP完整准确源码,给出KMP算法的准确的完整源码;
  6. 第六步份、一眼看出字符串的next数组各值,通过几个例子,让读者能根据字符串本身一眼判断出其next数组各值。

    力求让此文彻底让读者洞穿此KMP算法,所有原理,来龙去脉,让读者搞个通通透透(注意,本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算,其它部分如第三部分的代码实现二,第五部分,和第六部分的字符串下标i 皆是从1开始的)。

    在看本文之前,你心中如若对前缀和后缀这个两个概念有自己的理解,便最好了。有些东西比如此KMP算法需要我们反复思考,反复求解才行。个人写的关于KMP算法的第二篇文章为:六(续)、从KMP算法一步一步谈到BM算法;第一篇为:六、教你初步了解KMP算法、updated(文末链接)。ok,若有任何问题,恳请不吝指正。多谢。

第一部分、KMP算法初解

1普通字符串匹配BF算法与KMP算法的时间复杂度比较

    KMP算法是一种线性时间复杂的字符串匹配算法,它是对BF算法(Brute-Force,最基本的字符串匹配算法的)改进。对于给的原始串S和模式串P,需要从字符串S中找到字符串P出现的位置的索引。

BF算法的时间复杂度O(strlen(S) * strlen(T)),空间复杂度O(1)

KMP算法的时间复杂度O(strlen(S) + strlen(T)),空间复杂度O(strlen(T))

2BF算法与KMP算法的区别

    假设现在S串匹配到i位置,T串匹配到j位置。那么总的来说,两种算法的主要区别在于失配的情况下,对[j]的值做的处理

   BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符;如果失配,即S[i + j] != T[j]需要让i++,并且j=
0
,即每次匹配失败的情况下,模式串T相对于原始串S向右移动了一位。

    而KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++j++,继续匹配下一个字符;如果匹配失败,即S[i] != T[j],需要保持i不变,并且让j
= next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1(移动的实际位数j
- next[j]  >=1
),

    同时移动之后,i之前的部分(即S[i-j+1 ~ i-1]),和j=next[j]之前的部分(即T[0 ~ j-2])仍然相等。显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用! (失配的特殊情形,令j=next[j]导致j==0的时候,需要将i
++,否则此时没有移动模式串)

3、BF算法为什么要回溯

首先说一下为什么BF算法要回溯。如下两字符串匹配(恰如上面所述:BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符):

      i+jjT中的j++变,而动)

S:aaaacefghij

         j++

T:aaac 

如果不回溯的话就是从下一位开始比起:

aaaacefghij

        aaac

看到上面红颜色的没,如果不回溯的话,那么从a 的下一位比起。然而下述这种情况就漏了(正确的做法当然是要回溯:如果失配,即S[i + j] != T[j]需要让i++,并且j=
0
):

aaaacefghij

  aaac

    所以,BF算法要回溯,其代码如下:

  1. int Index(SString S, SString T, int pos) {  
  2.    //返回T在S中第pos个字符之后的位置  
  3.    i=pos; j=1;k=0;  
  4.   while ( i< = S[0] && j< = T[0] ) {  
  5.       if (S[i+k] = = T[j] ) {++k;  ++j;}   //继续比较后续字符  
  6.       else {i=i+1;   j=1; k=0;}      //指针回溯到 下一首位,重新开始  
  7.   }  
  8.   if(j>T[0]) return i;          //子串结束,说明匹配成功  
  9.   else return  0;  
  10. }//Index  

  不过,也有特殊情况可以不回溯,如下:
abcdefghij(主串)
abcdefg(模式串)
  即(模式串)没有相同的才不需要回溯。

4KMP 算法思想
    普通的字符串匹配算法必须要回溯。但回溯就影响了效率,回溯是由T串本身的性质决定的,是因为T串本身有前后'部分匹配'的性质。像上面所说如果主串为abcdef这样的,大没有回溯的必要。

    改进的地方也就是这里,我们从T串本身出发,事先就找准了T自身前后部分匹配的位置,那就可以改进算法。

    如果不用回溯,那模式串下一个位置从哪里开始呢?

    还是上面那个例子,T(模式串)ababc,如果c失配,那就可以往前移到aba最后一个a的位置,像这样:

...ababd...

   ababc

    ->ababc

这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在。这个当T[j]失配后,应该往前跳的值就是jnext,它是由T串本身固有决定的,与S(主串)无关

5、next数组的含义

重点来了。下面解释一下next数组的含义,这个也是KMP算法中比较不好理解的一点。

  令原始串为: S[i],其中0<=i<=n;模式串为: T[j],其中0<=j<=m

  假设目前匹配到如下位置

               S0,S1,S2,...,Si-j,Si-j+1...............,Si-1Si, Si+1,....,Sn

                                   T0,T1,.....................,Tj-1Tj, ..........

  ST的绿色部分匹配成功,恰好到SiTj的时候失配,如果要保持i不变,同时达到让模式串T相对于原始串S右移的话,可以更新j的值,让Si和新的Tj进行匹配,假设新的jnext[j]表示,即让Sinext[j]匹配,显然新的j值要小于之前的j值,模式串才会是右移的效果,也就是说应该有next[j]
<= j -1。那新的j值也就是next[j]应该是多少呢?我们观察如下的匹配:

      1)如果模式串右移1位(从简单的思考起,移动一位会怎么样),即next[j] = j - 1, 即让蓝色的SiTj-1匹配(注:省略号为未匹配部分)

               S0,S1,S2,...,Si-j,Si-j+1...............,Si-1Si, Si+1,....,Sn

                                   T0,T1,.....................,Tj-1Tj, .......... (T的划线部分和S划线部分相等【1】)

                                        T0,T1,.................Tj-2,Tj-1, ....... (移动后的T的划线部分和S的划线部分相等【2】)

        根据【1】【2】可以知道当next[j] =j -1,即模式串右移一位的时候,有T[0 ~ j-2] == T[1 ~ j-1],而这两部分恰好是字符串T[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串Tj前面部分的前缀和后缀相等部分的长度(好好揣摩这两个关键字概念:前缀、后缀,或者再想想,我的上一篇文章,从Trie树谈到后缀树中,后缀树的概念)。

      2)如果模式串右移2位,即next[j] = j - 2, 即让蓝色的SiTj-2匹配    

               S0,S1,...,Si-j,Si-j+1,Si-j+2...............,Si-1Si, Si+1,....,Sn

                                   T0,T1,T2,.....................,Tj-1Tj, ..........(T的划线部分和S划线部分相等【3】)

                                              T0,T1,...............,Tj-3,Tj-2,.........(移动后的T的划线部分和S的划线部分相等【4】)

        同样根据【3】【4】可以知道当next[j] =j -2,即模式串右移两位的时候,有T[0 ~ j-3] == T[2 ~ j-1]。而这两部分也恰好是字符串T[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串Tj前面部分的前缀和后缀相等部分的长度

     3)依次类推,可以得到如下结论:当发生失配的情况下,j的新值next[j]取决于模式串中T[0 ~ j-1]中前缀和后缀相等部分的长度, 并且next[j]恰好等于这个最大长度

    为此,请再允许我引用上文中的一段原文:KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++j++,继续匹配下一个字符;如果匹配失败,即S[i]
!= T[j],需要保持i不变,并且让j = next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1(移动的实际位数j
- next[j]  >=1
),

    同时移动之后,i之前的部分(即S[i-j+1 ~ i-1]),和j=next[j]之前的部分(即T[0 ~ j-2])仍然相等。显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用! (失配的特殊情形,令j=next[j]导致j==0的时候,需要将i
++,否则此时没有移动模式串)。”

    于此,也就不难理解了我的关于KMP算法的第二篇文章之中:当匹配到S[i] != P[j]的时候有 S[i-j…i-1] = P[0…j-1]. 如果下面用j_next去匹配,则有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。此过程如下图3-1所示。

  当匹配到S[i] != P[j]时,S[i-j…i-1] = P[0…j-1]

S: 0 … i-j … i-1 i …

P:       0 …   j-1 j …

  如果下面用j_next去匹配,则有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。
所以在P中有如下匹配关系(获得这个匹配关系的意义是用来求next数组)

P: 0 … j-j_next  .…j-1_    …

P:        0    … .j_next-1 …

  所以,根据上面两个步骤,推出下一匹配位置j_next:

S: 0 … i-j … i-j_next …   i-1      i …

P:                   0   … j_next-1 j_next …

             图3-1 求j-next(最大的值)的三个步骤

    下面,我们用变量k来代表求得的j_next的最大值,即k表示这S[i]、P[j]不匹配时P中下一个用来匹配的位置,使得P[0…k-1] = P[j-k…j-1],而我们要尽量找到这个k的最大值。”。

      根据上文的【1】与【2】的匹配情况,可得第二篇文章之中所谓的k=1(如aaaa的形式),根据上文的【3】与【4】的匹配情况,k=2(如abab的形式)。

     所以,归根究底,KMP算法的本质便是:针对待匹配的模式串的特点,判断它是否有重复的字符,从而找到它的前缀与后缀,进而求出相应的Next数组,最终根据Next数组而进行KMP匹配。接下来,进入本文的第二部分。

第二部分、next数组求法的来龙去脉与KMP算法的源码

    本部分引自个人此前的关于KMP算法的第二篇文章:六之续、由KMP算法谈到BM算法。前面,我们已经知道即不能让P[j]=P[next[j]]成立成立。不能再出现上面那样的情况啊!即不能有这种情况出现:P[3]=b,而竟也有P[next[3]]=P[1]=b

    正如在第二篇文章中,所提到的那样:“这里读者理解可能有困难的是因为文中,时而next,时而nextval,把他们的思维搞混乱了。其实next用于表达数组索引,而nextval专用于表达next数组索引下的具体各值,区别细微。至于文中说不允许P[j]=P[next[j]
]出现,是因为已经有P[3]=b与S[i]匹配败,而P[next[3]]=P1=b,若再拿P[1]=b去与S[i]匹配则必败。”--六之续、由KMP算法谈到BM算法。

   又恰恰如上文中所述:“模式串T相对于原始串S向右移动了至少1(移动的实际位数j
- next[j]  >=1
)

    ok,求next数组的get_nextval函数正确代码如下:

  1. //代码4-1    
  2. //修正后的求next数组各值的函数代码    
  3. void get_nextval(char const* ptrn, int plen, int* nextval)    
  4. {    
  5.     int i = 0;     
  6.     nextval[i] = -1;    
  7.     int j = -1;    
  8.     while( i < plen-1 )    
  9.     {    
  10.         if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分    
  11.         {    
  12.             ++i;    
  13.             ++j;    
  14.             //修正的地方就发生下面这4行    
  15.             if( ptrn[i] != ptrn[j] ) //++i,++j之后,再次判断ptrn[i]与ptrn[j]的关系    
  16.                 nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。    
  17.             else    
  18.                 nextval[i] = nextval[j];    
  19.         }    
  20.         else                                 //循环的else部分    
  21.             j = nextval[j];    
  22.     }    
  23. }    

    举个例子,举例说明下上述求next数组的方法。
S a b a b a b c
P a b a b c
S[4] != P[4]
    那么下一个和S[4]匹配的位置是k=2(也即P[next[4]])。此处的k=2也再次佐证了上文第3节开头处关于为了找到下一个匹配的位置时k的求法。上面的主串与模式串开头4个字符都是“abab”,所以,匹配失效后下一个匹配的位置直接跳两步继续进行匹配。
S a b a b a b c
P      a b a b c
匹配成功

P的next数组值分别为-1 0 -1 0 2

    next数组各值怎么求出来的呢?分以下五步:

  1. 初始化:i=0,j=-1,nextval[0] = -1由于j == -1,进入上述循环的if部分,++i得i=1,++j得j=0,且ptrn[i] != ptrn[j](即a!=b)),所以得到第二个next值即nextval[1] = 0;
  2. i=1,j=0,进入循环esle部分,j=nextval[j]=nextval[0]=-1;
  3. 进入循环的if部分,++i,++j,i=2,j=0,因为ptrn[i]=ptrn[j]=a,所以nextval[2]=nextval[0]=-1;
  4. i=2, j=0, 由于ptrn[i]=ptrn[j],再次进入循环if部分,所以++i=3,++j=1,因为ptrn[i]=ptrn[j]=b,所以nextval[3]=nextval[1]=0;
  5. i=3,j=1,由于ptrn[i]=ptrn[j]=b,所以++i=4,++j=2,退出循环。

    这样上例中模式串的next数组各值最终应该为:

            图4-1 正确的next数组各值
next数组求解的具体过程如下:
    初始化:nextval[0] = -1,我们得到第一个next值即-1.

            图4-2 初始化第一个next值即-1

    i = 0,j = -1,由于j == -1,进入上述循环的if部分,++i得i=1,++j得j=0,且ptrn[i] != ptrn[j](即a!=b)),所以得到第二个next值即nextval[1] = 0;

           图4-3 第二个next值0

   上面我们已经得到,i= 1,j = 0,由于不满足条件j == -1 || ptrn[i] == ptrn[j],所以进入循环的esle部分,得j = nextval[j] = -1;此时,仍满足循环条件,由于i = 1,j = -1,因为j == -1,再次进入循环的if部分,++i得i=2,++j得j=0,由于ptrn[i] == ptrn[j](即ptrn[2]=ptrn[0],也就是说第1个元素和第三个元素都是a),所以进入循环if部分内嵌的else部分,得到nextval[2] = nextval[0]
= -1;

         图4-4 第三个next数组元素值-1

    i = 2,j = 0,由于ptrn[i] == ptrn[j],进入if部分,++i得i=3,++j得j=1,所以ptrn[i] == ptrn[j](ptrn[3]==ptrn[1],也就是说第2个元素和第4个元素都是b),所以进入循环if部分内嵌的else部分,得到nextval[3] = nextval[1] = 0;

         图4-5 第四个数组元素值0
    如果你还是没有弄懂上述过程是怎么一回事,请现在拿出一张纸和一支笔出来,一步一步的画下上述过程。相信我,把图画出来了之后,你一定能明白它的。
    然后,我留一个问题给读者,为什么上述的next数组要那么求?有什么原理么?

    提示:我们从上述字符串abab 各字符的next值-1 0 -1 0,可以看出来,根据求得的next数组值,偷用前缀、后缀的概念,一定可以判断出在abab之中,前缀和后缀相同,即都是ab,反过来,如果一个字符串的前缀和后缀相同,那么根据前缀和后缀依次求得的next各值也是相同的。

  • 5、利用求得的next数组各值运用Kmp算法

    Ok,next数组各值已经求得,万事俱备,东风也不欠了。接下来,咱们就要应用求得的next值,应用KMP算法来匹配字符串了。还记得KMP算法是怎么一回事吗?容我再次引用下之前的KMP算法的代码,如下:

  1. //代码5-1    
  2. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数    
  3. //输入:src, slen主串    
  4. //输入:patn, plen模式串    
  5. //输入:nextval KMP算法中的next函数值数组    
  6. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
  7. {    
  8.     int i = pos;    
  9.     int j = 0;    
  10.     while ( i < slen && j < plen )    
  11.     {    
  12.         if( j == -1 || src[i] == patn[j] )    
  13.         {    
  14.             ++i;    
  15.             ++j;    
  16.         }    
  17.         else    
  18.         {    
  19.             j = nextval[j];              
  20.             //当匹配失败的时候直接用p[j_next]与s[i]比较,    
  21.             //下面阐述怎么求这个值,即匹配失效后下一次匹配的位置    
  22.         }    
  23.     }    
  24.     if( j >= plen )    
  25.         return i-plen;    
  26.     else    
  27.         return -1;    
  28. }    

我们上面已经求得的next值,如下:

        图5-1 求得的正确的next数组元素各值

    以下是匹配过程,分三步:
    第一步:主串和模式串如下,S[3]与P[3]匹配失败。

               图5-2 第一步,S[3]与P[3]匹配失败
    第二步:S[3]保持不变,P的下一个匹配位置是P[next[3]],而next[3]=0,所以P[next[3]]=P[0],即P[0]与S[3]匹配。在P[0]与S[3]处匹配失败。

                图5-3 第二步,在P[0]与S[3]处匹配失败

    第三步:与上文中第3小节末的情况一致。由于上述第三步中,P[0]与S[3]还是不匹配。此时i=3,j=nextval[0]=-1,由于满足条件j==-1,所以进入循环的if部分,++i=4,++j=0,即主串指针下移一个位置,从P[0]与S[4]处开始匹配。最后j==plen,跳出循环,输出结果i-plen=4(即字串第一次出现的位置),匹配成功,算法结束。

                图5-4 第三步,匹配成功,算法结束
    所以,综上,总结上述三步为

  1. 开始匹配,直到P[3]!=S[3],匹配失败;
  2. nextval[3]=0,所以P[0]继续与S[3]匹配,再次匹配失败;
  3. nextval[0]=-1,满足循环if部分条件j==-1,所以,++i,++j,主串指针下移一个位置,从P[0]与S[4]处开始匹配,最后j==plen,跳出循环,输出结果i-plen=4,算法结束。

第三部分、KMP算法的两种实现

代码实现一:   

    根据上文中第二部分内容的解析,完整写出KMP算法的代码已经不是难事了,如下:

  1. //copyright@2011 binghu and july  
  2. #include "StdAfx.h"  
  3. #include <string>  
  4. #include <iostream>  
  5. using namespace std;  
  6.   
  7. //代码4-1    
  8. //修正后的求next数组各值的函数代码    
  9. void get_nextval(char const* ptrn, int plen, int* nextval)    
  10. {    
  11.     int i = 0;  //注,此处与下文的代码实现二不同的是,i是从0开始的(代码实现二i从1开始)     
  12.     nextval[i] = -1;    
  13.     int j = -1;    
  14.     while( i < plen-1 )    
  15.     {    
  16.         if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分    
  17.         {    
  18.             ++i;    
  19.             ++j;    
  20.             //修正的地方就发生下面这4行    
  21.             if( ptrn[i] != ptrn[j] ) //++i,++j之后,再次判断ptrn[i]与ptrn[j]的关系    
  22.                 nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。    
  23.             else    
  24.                 nextval[i] = nextval[j];    
  25.         }    
  26.         else                                 //循环的else部分    
  27.             j = nextval[j];    
  28.     }    
  29. }    
  30.   
  31. void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)  
  32. {  
  33.     cout<<src_index<<"t"<<src<<endl;  
  34.     cout<<pstr_index<<"t";  
  35.     forint i = 0; i < src_index-pstr_index; ++i )  
  36.         cout<<" ";  
  37.     cout<<pstr<<endl;  
  38.     cout<<endl;  
  39. }  
  40.   
  41. //代码5-1    
  42. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数    
  43. //输入:src, slen主串    
  44. //输入:patn, plen模式串    
  45. //输入:nextval KMP算法中的next函数值数组    
  46. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
  47. {    
  48.     int i = pos;    
  49.     int j = 0;    
  50.     while ( i < slen && j < plen )    
  51.     {    
  52.         if( j == -1 || src[i] == patn[j] )    
  53.         {    
  54.             ++i;    
  55.             ++j;    
  56.         }    
  57.         else    
  58.         {    
  59.             j = nextval[j];              
  60.             //当匹配失败的时候直接用p[j_next]与s[i]比较,    
  61.             //下面阐述怎么求这个值,即匹配失效后下一次匹配的位置    
  62.         }    
  63.     }    
  64.     if( j >= plen )    
  65.         return i-plen;    
  66.     else    
  67.         return -1;    
  68. }    
  69.   
  70. int   main()  
  71. {  
  72.     std::string src = "aabcabcebafabcabceabcaefabcacdabcab";  
  73.     std::string prn = "abac";  
  74.   
  75.     int* nextval = new int[prn.size()];  
  76.     //int* next = new int[prn.size()];  
  77.     get_nextval(prn.data(), prn.size(), nextval);  
  78.     //get_next(prn.data(), prn.size(), next);  
  79.   
  80.     forint i = 0; i < prn.size(); ++i )  
  81.         cout<<nextval[i]<<"t";  
  82.     cout<<endl;  
  83.       
  84.     cout<<"result sub str: "<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;  
  85.     system("pause");  
  86.   
  87.     delete[] nextval;  
  88.     return 0;  
  89. }   

    运行结果,如下图所示:

代码实现二

     再给出代码实现二之前,让我们再次回顾下关于KMP算法的第一篇文章中的部分内容

第二节、KMP算法

2.1、 覆盖函数(overlay_function)

    覆盖函数所表征的是pattern本身的性质,可以让为其表征的是pattern从左开始的所有连续子串的自我覆盖程度。比如如下的字串,abaabcaba

    可能上面的图令读者理解起来还是不那么清晰易懂,其实很简单,针对字符串abaabcaba

a(-1) b(-1)a(0) a0 b(1) c(-1) a(0) b(1)a(2)

解释:

  1. 初始化为-1  
  2. b与a不同为-1   
  3. 与第一个字符a相同为0   
  4. 还是a为0   
  5. 后缀ab与前缀ab两个字符相同为1 
  6. 前面并无前缀c为-1  
  7. 与第一个字符同为0  
  8. 后缀ab前缀ab为1 
  9. 前缀aba后缀aba为2

    由于计数是从0始的,因此覆盖函数的值为0说明有1个匹配,对于从0还是从来开始计数是偏好问题,具体请自行调整,其中-1表示没有覆盖,那么何为覆盖呢,下面比较数学的来看一下定义,比如对于序列

  a0a1...aj-1 aj

要找到一个k,使它满足

  a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

    而没有更大的k满足这个条件,就是说要找到尽可能大k,使pattern前k字符与后k字符相匹配,k要尽可能的大,原因是如果有比较大的k存在。

    但若我们选择较小的满足条件的k,那么当失配时,我们就会使pattern向右移动的位置变大,而较少的移动位置是存在匹配的,这样我们就会把可能匹配的结果丢失。比如下面的序列,

    在红色部分失配,正确的结果是k=1的情况,把pattern右移4位,如果选择k=0,右移5位则会产生错误。计算这个overlay函数的方法可以采用递推,可以想象如果对于pattern的前j个字符,如果覆盖函数值为k

    a0a1...ak-1ak=aj-kaj-k+1...aj-1aj
则对于pattern的前j+1序列字符,则有如下可能
    ⑴     pattern[k+1]==pattern[j+1] 此时overlay(j+1)=k+1=overlay(j)+1
    ⑵     pattern[k+1]≠pattern[j+1] 此时只能在pattern前k+1个子符组所的子串中找到相应的overlay函数,h=overlay(k),如果此时pattern[h+1]==pattern[j+1],则overlay(j+1)=h+1否则重复(2)过程.

下面给出一段计算覆盖函数的代码:

  1. //copyright@ staurman  
  2. //updated@2011 July  
  3. #include "StdAfx.h"  
  4. #include<iostream>  
  5. #include<string>  
  6. using namespace std;  
  7.   
  8. //solve to the next array  
  9. void compute_overlay(const string& pattern)  
  10. {  
  11.     const int pattern_length = pattern.size();  
  12.     int *overlay_function = new int[pattern_length];  
  13.     int index;  
  14.     overlay_function[0] = -1;  
  15.     for(int i=1;i<pattern_length;++i)      
  16.         //注,与上文代码段一不同的是,此处i是从1开始的,所以,下文中运用俩种方法求出来的next数组各值会有所不同  
  17.     {  
  18.         index = overlay_function[i-1];  
  19.         //store previous fail position k to index;  
  20.   
  21.         while(index>=0 && pattern[i]!=pattern[index+1])  
  22.         {  
  23.             index = overlay_function[index];  
  24.         }  
  25.         if(pattern[i]==pattern[index+1])  
  26.         {  
  27.             overlay_function[i] = index + 1;    
  28.         }  
  29.         else  
  30.         {  
  31.             overlay_function[i] = -1;  
  32.         }  
  33.     }  
  34.     for(int i=0;i<pattern_length;++i)  
  35.     {  
  36.         cout<<overlay_function[i]<<endl;  
  37.     }  
  38.     delete[] overlay_function;  
  39. }  
  40.   
  41. //abaabcaba  
  42. int main()  
  43. {  
  44.     string pattern = "abaabcaba";  
  45.     compute_overlay(pattern);  
  46.     system("pause");  
  47.     return 0;  
  48. }  

    运行结果如下所示:

2.2、kmp算法
     有了覆盖函数,那么实现kmp算法就是很简单的了,我们的原则还是从左向右匹配,但是当失配发生时,我们不用把target_index向回移动,target_index前面已经匹配过的部分在pattern自身就能体现出来,只要动pattern_index就可以了。

当发生在j长度失配时,只要把pattern向右移动j-overlay(j)长度就可以了。

     如果失配时pattern_index==0,相当于pattern第一个字符就不匹配,这时就应该把target_index加1,向右移动1位就可以了。

    ok,下图就是KMP算法的过程(红色即是采用KMP算法的执行过程):

    (另一作者saturnman发现,在上述KMP匹配过程图中,index=8和index=11处画错了。还有,anaven也早已发现,index=3处也画错了。非常感谢。但图已无法修改,见谅)

KMP 算法可在O(n+m)时间内完成全部的串的模式匹配工作。

    OK,下面此前写的关于KMP算法的第一篇文章中的源码:

  1. //copyright@ saturnman  
  2. //updated@ 2011 July  
  3. #include "stdafx.h"  
  4. #include<iostream>  
  5. #include<string>  
  6. #include <vector>  
  7. using namespace std;  
  8.   
  9. int kmp_find(const string& target,const string& pattern)  
  10. {  
  11.     const int target_length=target.size();  
  12.     const int pattern_length=pattern.size();  
  13.     int* overlay_value=new int[pattern_length];  
  14.     overlay_value[0]=-1;        //remember:next array's first number was -1.  
  15.     int index=0;  
  16.   
  17.     //next array  
  18.     for (int i=1;i<pattern_length;++i)  
  19.         //注,此处的i是从1开始的  
  20.     {  
  21.         index=overlay_value[i-1];  
  22.         while (index>=0 && pattern[index+1]!=pattern[i])  //remember:!=  
  23.         {  
  24.             index=overlay_value[index];  
  25.         }  
  26.         if(pattern[index+1] == pattern[i])  
  27.         {  
  28.             overlay_value[i]=index+1;  
  29.         }  
  30.         else  
  31.         {  
  32.             overlay_value[i]=-1;  
  33.         }  
  34.     }  
  35.   
  36.     //mach algorithm start  
  37.     int pattern_index=0;  
  38.     int target_index=0;  
  39.     while (pattern_index<pattern_length && target_index<target_length)  
  40.     {  
  41.         if (target[target_index] == pattern[pattern_index])  
  42.         {  
  43.             ++target_index;  
  44.             ++pattern_index;  
  45.         }   
  46.         else if(pattern_index==0)  
  47.         {  
  48.             ++target_index;  
  49.         }  
  50.         else  
  51.         {  
  52.             pattern_index=overlay_value[pattern_index-1]+1;  
  53.         }  
  54.     }  
  55.     if (pattern_index==pattern_length)  
  56.     {  
  57.         return target_index-pattern_index;  
  58.     }   
  59.     else  
  60.     {  
  61.         return -1;  
  62.     }  
  63.     delete [] overlay_value;  
  64. }  
  65.   
  66. int main()  
  67. {  
  68.     string sourc="ababc";  
  69.     string pattern="abc";  
  70.     cout<<kmp_find(sourc,pattern)<<endl;  
  71.     system("pause");  
  72.     return 0;  
  73. }  

    由于是abc跟ababc匹配,那么将返回匹配的位置“2”,运行结果如所示:

第四部分、测试

    针对上文中第三部分的两段代码测试了下,纠结了,两种求next数组的方法对同一个字符串求next数组各值,得到的结果竟然不一样,如下二图所示:

    1、两种方法对字符串abab求next数组各值比较:

    2、两种对字符串abaabcaba求next数组各值比较:

    为何会这样呢,其实很简单,上文中已经有所说明了,代码实现一的i 是从0开始的,代码实现二的i 是从1开始的。但从最终的运行结果来看,暂时还是以代码实现段二为准。

第五部分、KMP完整准确源码

    求next数组各值的方法为:

  1. //copyright@ staurman  
  2. //updated@2011 July  
  3. #include "StdAfx.h"  
  4. #include<iostream>  
  5. #include<string>  
  6. using namespace std;  
  7.   
  8. //solve to the next array  
  9. void compute_overlay(const string& pattern)  
  10. {  
  11.     const int pattern_length = pattern.size();  
  12.     int *overlay_function = new int[pattern_length];  
  13.     int index;  
  14.     overlay_function[0] = -1;  
  15.     for(int i=1;i<pattern_length;++i)  
  16.     {  
  17.         index = overlay_function[i-1];  
  18.         //store previous fail position k to index;  
  19.   
  20.         while(index>=0 && pattern[i]!=pattern[index+1])  
  21.         {  
  22.             index = overlay_function[index];  
  23.         }  
  24.         if(pattern[i]==pattern[index+1])  
  25.         {  
  26.             overlay_function[i] = index + 1;    
  27.         }  
  28.         else  
  29.         {  
  30.             overlay_function[i] = -1;  
  31.         }  
  32.     }  
  33.     for(int i=0;i<pattern_length;++i)  
  34.     {  
  35.         cout<<overlay_function[i]<<endl;  
  36.     }  
  37.     delete[] overlay_function;  
  38. }  
  39.   
  40. //abaabcaba  
  41. int main()  
  42. {  
  43.     string pattern = "abaabcaba";  
  44.     compute_overlay(pattern);  
  45.     system("pause");  
  46.     return 0;  
  47. }  

    运行结果入下图所示:abab的next数组各值是-1,-1,0,1,而非本文第二部分所述的-1,0,-1,0。为什么呢?难道是搬石头砸了自己的脚?

    NO,上文第四部分末已经详细说明,上处代码i 从0开始,本文第二部分代码i 从1开始。

    KMP算法完整源码,如下:

  1. //copyright@ saturnman  
  2. //updated@ 2011 July  
  3. #include "stdafx.h"  
  4. #include<iostream>  
  5. #include<string>  
  6. #include <vector>  
  7. using namespace std;  
  8.   
  9. int kmp_find(const string& target,const string& pattern)  
  10. {  
  11.     const int target_length=target.size();  
  12.     const int pattern_length=pattern.size();  
  13.     int* overlay_value=new int[pattern_length];  
  14.     overlay_value[0]=-1;        //remember:next array's first number was -1.  
  15.     int index=0;  
  16.   
  17.     //next array  
  18.     for (int i=1;i<pattern_length;++i)  
  19.         //注,此处的i是从1开始的  
  20.     {  
  21.         index=overlay_value[i-1];  
  22.         while (index>=0 && pattern[index+1]!=pattern[i])    
  23.         {  
  24.             index=overlay_value[index];  
  25.         }  
  26.         if(pattern[index+1] == pattern[i])  
  27.         {  
  28.             overlay_value[i]=index+1;  
  29.         }  
  30.         else  
  31.         {  
  32.             overlay_value[i]=-1;  
  33.         }  
  34.     }  
  35.   
  36.     //mach algorithm start  
  37.     int pattern_index=0;  
  38.     int target_index=0;  
  39.     while (pattern_index<pattern_length && target_index<target_length)  
  40.     {  
  41.         if (target[target_index] == pattern[pattern_index])  
  42.         {  
  43.             ++target_index;  
  44.             ++pattern_index;  
  45.         }   
  46.         else if(pattern_index==0)  
  47.         {  
  48.             ++target_index;  
  49.         }  
  50.         else  
  51.         {  
  52.             pattern_index=overlay_value[pattern_index-1]+1;  
  53.         }  
  54.     }  
  55.     if (pattern_index==pattern_length)  
  56.     {  
  57.         return target_index-pattern_index;  
  58.     }   
  59.     else  
  60.     {  
  61.         return -1;  
  62.     }  
  63.     delete [] overlay_value;  
  64. }  
  65.   
  66. int main()  
  67. {  
  68.     string sourc="ababc";  
  69.     string pattern="abc";  
  70.     cout<<kmp_find(sourc,pattern)<<endl;  
  71.     system("pause");  
  72.     return 0;  
  73. }  

    运行结果如下:

第六部分、一眼看出字符串的next数组各值

    上文已经用程序求出了一个字符串的next数组各值,接下来,稍稍演示下,如何一眼大致判断出next数组各值,以及初步判断某个程序求出的next数组各值是不是正确的。有一点务必注意:下文中的代码全部采取代码实现二,即i是从1开始的

  • 1、对字符串aba求next数组各值,各位可以先猜猜,-1,...,aba中,a初始化为-1,第二个字符b与a不同也为-1,最后一个字符和第一个字符都是a,所以,我猜其next数组各值应该是-1,-1,0,结果也不出所料,如下图所示:

  • 2、字符串“abab”呢,不用猜了,我已经看出来了,当然上文中代码实现一和代码实现二都已经求出来了。如果i 是1开始的话,那么next数组各值将如代码实现二所运行的那样,将是:-1,-1,0,1;
  • 3、字符串“abaabcaba”呢,next数组如上第三部分代码实现二所述,为-1,-1,0,0,1,-1,0,1,2;
  • 4、字符串“abcdab”呢,next数组各值将是-1,-1,-1,-1,0,1;
  • 5、字符串“abcdabc”呢,next数组各值将是-1,-1,-1,-1,0,1,2;
  • 6、字符串“abcdabcd”呢,那么next数组各值将是-1,-1,-1,-1,0,1,2,3;

    怎么样,看出规律来了没?呵呵,可以用上述第五部分中求next数组的方法自个多试探几次,相信,很快,你也会跟我一样,不用计算,一眼便能看出某个字符串的next数组各值了。如此便恭喜你,理解了next数组的求法,KMP算法也就算是真真正正彻彻底底的理解了。完。

相关链接

  1. KMP之第二篇文章:六(续)、从KMP算法一步一步谈到BM算法
  2. KMP之第一篇文章:六、教你初步了解KMP算法、updated

后记 

     相信,看过此文后,无论是谁,都一定可以把KMP算法搞懂了(但万一还是有读者没有搞懂,那怎么办呢?还有最后一个办法:把本文打印下来,再仔细琢磨。如果是真真正正想彻底弄懂某一个东西,那么必须付出些代价。但万一要是打印下来了却还是没有弄懂呢?那来北京找我吧,我手把手教你。祝好运)。
    在结束全文之前,谈两点感悟:
  1. 语言->数据结构->算法:语言是基础,够啃一辈子,基本的常见的数据结构得了如指掌,最后才是算法。除了算法之外,有更多更重要且更值得学习的东西(最重要的是,学习如何编程)。切勿盲目跟风,找准自己的兴趣点,和领域才是关键。这跟选择职位、与领域并持久做下去,比选择公司更重要一样。选择学什么东西不重要,重要的是你的兴趣。
  2. 修订这篇文章之时,个人接触KMP都有一年了,学算法也刚好快一年。想想阿,我弄一个KMP,弄了近一年了,到今天才算是真正彻底理解其思想,可想而知,当初创造这个算法的k、m、p三人是何等不易。我想,有不少读者是因为我的出现而想学算法的,但不可急功近利,切勿妄想算法速成。早已说过,学算法先修心。
     OK,文中有关任何问题或错误,烦请不吝赐教与指正。谢谢,完。
    July、二零一一年十二月五日中午。