字符串的模式匹配
字符串定位操作通常被称为模式匹配，是各种字符串处理系统中最重要的操作之一。 本文主要介绍两种常用的实现算法：
1、暴力匹配
2、KMP算法
1 .暴力匹配
时间复杂度为o(n*m )； n是主串长度，m是图案串长度
算法的基本思想：
从主字符串的开始位置(或指定位置)开始与模式字符串的第一个字符进行比较，如果相等，则继续一个字符一个字符地比较后续字符； 否则，从主字符串的下一个字符开始重新与模式串的字符进行比较。 模式列匹配成功，返回主列中第一个模式列字符出现的位置，或依次类推直到模式列匹配失败，这里约定返回-1；
//伪代码
intbruteforcestringmatch (字符串源，字符串模式) )。
{
i=0； j=0； wile(Islenj
{if(s(I )==p (j ) ) I； j； Elsei=I-(j-1 )； //追溯上次匹配的开始位置的下位
j=0；
}if(j==plen )返回I-j； //匹配成功
else
返回- 1； //匹配失败
}
实现代码：
1 publicstaticintbruteforcestringmatch (string source，String pattern )2 {3 int slen=source.length； 4 int plen=pattern.length (； 5 char[] s=source.toCharArray (； 6 char[] p=pattern.toCharArray (； 7 int i=0； 8 int j=0； 9
10if(Slen
12 else
13{14}while(Islenj
17 {18 i； 19 j； 20 ) 21else
2{23I=I-(j-1 )； //i从主串的上次追溯到匹配下一个位置的位置
24 j=0； //j复位，模式列从一开始就再次匹配
25 ) 27if(j==plen )//匹配成功
28返回I-j； 29 else
30返回- 1； //匹配失败
31 }32 }
视图代码
2.KMP算法
KMP算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同时发现的，因此被命名为KMP算法。
该算法可以在o(nm )的时间量级上完成串的模式匹配。
主要是改进暴力匹配中I回溯的操作。 KMP算法在一次匹配过程中字符不同时，不直接回溯I，而是使用已经得到的“部分匹配”结果将模式串向右移动(j-next[k] )。 稍后将详细说明next[k]的计算过程。
//伪代码
intkmpstringmatch (字符串源，字符串模式)。
{
i=0；
j=1； wile(Islenj
{if(j==0||s[I]==p[j] ) I； j； elsej=next[j]；
}if(j==plen )返回I-j； else
返回- 1；
}
实现代码：
1 publicstaticintkmpstringmatch (字符串源，字符串模式)2 {3 int i=0； 4 int j=0； 5 char[] s=source.toCharArray (； 6 char[] p=pattern.toCharArray (； 7 int slen=s.length； 8 int plen=p.length； 9int[]next=getnext(p； 10while(Islenj
18 {19 //喂j！ 如果=-1且当前字符匹配失败，则不更改I，将20 //j=next[j] (即图案列)向右移动j - next[j]个单位
21 j=next[j]； 22 ) 24if(j==plen ) 25返回I-j； 26 else
27返回- 1； 28 }
视图代码
那么，next[k]是怎么计算的呢？
获取next[k]数组计算的两种方法之一
种是递归，一种对递归优化，第一种对应的就是KMP算法，第二种就是优化的KMP算法。next函数值仅取决于模式串本身而和主串无关。
有很多讲next函数值计算办法的资料，在此我想用一种直观的比较容易理解的办法来表达。
举个栗子：现在有一个模式串abab
模式串的各个字串
前缀
后缀
最大公共元素长度
a
null
null
0
ab
a
b
0
aba
a,ab
a,ba
1
abab
a,ab,aba
b,ab,bab
2
next函数值的实现：
private static int[] getNext(char[] p)
{/*** 已知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; //这里采用-1做标识
while(j < plen -1)
{if(k == -1 || p[j] ==p[k])
{++k;++j;
next[j]=k;
}else{
k=next[k];
}
}returnnext;
}
View Code
国际惯例贴上源代码：
importjava.util.Scanner;public classPatternString {public static intbruteForceStringMatch(String source, String pattern)
{int slen =source.length();int plen =pattern.length();char[] s =source.toCharArray();char[] p =pattern.toCharArray();int i = 0;int j = 0;if(slen
else{while(i < slen && j
{if(s[i] == p[j]) //如果i,j位置上的字符匹配成功就继续向后匹配
{++i;++j;
}else{
i= i - (j -1); //i回溯到主串上一次开始匹配下一个位置的地方
j = 0; //j重置，模式串从开始再次进行匹配
}
}if(j == plen) //匹配成功
return i -j;else
return -1; //匹配失败
}
}public static intkmpStringMatch(String source, String pattern)
{int i = 0;int j = 0;char[] s =source.toCharArray();char[] p =pattern.toCharArray();int slen =s.length;int plen =p.length;int[] next =getNext(p);while(i < slen && j
{if(j == -1 || s[i] ==p[j])
{++i;++j;
}else{//如果j != -1且当前字符匹配失败，则令i不变，//j = next[j],即让pattern模式串右移j - next[j]个单位
j =next[j];
}
}if(j ==plen)return i -j;else
return -1;
}private static int[] getNext(char[] p)
{/*** 已知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; //这里采用-1做标识
while(j < plen -1)
{if(k == -1 || p[j] ==p[k])
{++k;++j;
next[j]=k;
}else{
k=next[k];
}
}
System.out.println("next函数值：");for(int ii = 0;ii
{
System.out.print(next[ii]+ " ");
}
System.out.println();returnnext;
}public static voidmain(String[] args) {
Scanner sc= newScanner(System.in);
String a=sc.nextLine();
String b=sc.nextLine();
System.out.println(bruteForceStringMatch(a, b));
System.out.println(kmpStringMatch(a, b));
}
}
View Code