kmpjava算法代码 kmp算法应用实例

KMP算法如下 要求时间：50MS内 大牛求教

不要用while(istrlen(p))与while(Istrlen(s))，这样每进行一次循环就要重新计算串的长度，会把本身是O(n)的算法变O(n^2)的。t=strlen(s);while(it) { } 这样子就行了

创新互联建站-专业网站定制、快速模板网站建设、高性价比桥东网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式桥东网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖桥东地区。费用合理售后完善，10年实体公司更值得信赖。

跪求大神写一段代码，采用KMP算法，在主串中求模式串的next函数值！主串：abcabcd 模式串bcd！跪求.....

求next程序代码：

void  getNext(char*p,int*next)

{   

int   j,k;   

next[0]=-1; j=0;k=-1;   

while(jstrlen(p)-1)

{       

  if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]       

  {           

       j++;           

       k++;           

       next[j]=k;       

  }       

  else          //p[j]!=p[k]           

      k=next[k];   

}

} 

KMP算法主程序：

int   KMPMatch(char*s, char*p)

{   

int    next[100];   

int    i,j;  i=0;  j=0;   

getNext( p, next );   

while( i  strlen(s) ){       

  if(j==-1||s[i]==p[j])       

  {           

      i++;           

      j++;       

  }

  else

  {           

      j=next[j];       //消除了指针i的回溯       

  }       

  if(j==strlen(p))           

      return    i-strlen(p);   

}   

return-1;

} 

java kmp算法中的 kmp 是什么意思？

kmp算法

一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

完全掌握KMP算法思想

学过数据结构的人，都对KMP算法印象颇深。尤其是新手，更是难以理解其涵义，搞得一头雾水。今天我们就来面对它，不将它彻底搞懂，誓不罢休。

如今，大伙基本上都用严蔚敏老师的书，那我就以此来讲解KMP算法。(小弟正在备战考研，为了节省时间，很多课本上的话我都在此省略了，以后一定补上。)

严老的《数据结构》79页讲了基本的匹配方法，这是基础。先把这个搞懂了。

80页在讲KMP算法的开始先举了个例子，让我们对KMP的基本思想有了最初的认识。目的在于指出“由此，在整个匹配的过程中，i指针没有回溯，”。

我们继续往下看：

现在讨论一般情况。

假设 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’

把课本上的这一段看完后，继续

现在我们假设 主串第i个字符与模式串的第j(j=m)个字符‘失配’后，主串第i个字符与模式串的第k(kj)个字符继续比较

此时，s(i)≠p(j), 有

主串： S(1)…… s(i-j+1)…… s(i-1) s(i) ………….

|| (相配) || ≠(失配)

匹配串： P(1) ……. p(j-1) p(j)

由此，我们得到关系式

‘p(1) p(2) p(3)…..p(j-1)’ = ’ s(i-j+1)……s(i-1)’

由于s(i)≠p(j)，接下来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在 k’k 满足下列关系式：(kj),

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(i-k+1)s(i-k+2)……s(i-1)’

即：

主串： S(1)……s(i-k +1) s(i-k +2) ……s(i-1) s(i) ………….

|| (相配) || || ?(有待比较)

匹配串： P(1) p(2) …… p(k-1) p(k)

现在我们把前面总结的关系综合一下

有：

S(1)…s(i-j +1)… s(i-k +1) s(i-k +2) …… s(i-1) s(i) ……

|| (相配) || || || ≠(失配)

P(1) ……p(j-k+1) p(j-k+2) ….... p(j-1) p(j)

|| (相配) || || ?(有待比较)

P(1) p(2) ……. p(k-1) p(k)

由上，我们得到关系：

‘p(1) p(2) p(3)…..p(k-1)’ = ’ s(j-k+1)s(j-k+2)……s(j-1)’

接下来看“反之，若模式串中存在满足式(4-4)。。。。。。。”这一段。看完这一段，如果下面的看不懂就不要看了。直接去看那个next函数的源程序。(伪代码)

K 是和next有关系的，不过在最初看的时候，你不要太追究k到底是多少，至于next值是怎么求出来的，我教你怎么学会。

课本83页不是有个例子吗？就是 图4.6

你照着源程序，看着那个例子慢慢的推出它来。看看你做的是不是和课本上正确的next值一样。

然后找几道练习题好好练练，一定要做熟练了。现在你的脑子里已经有那个next算法的初步思想了，再回去看它是怎么推出来的，如果还看不懂，就继续做练习，做完练习再看。相信自己！！！

附：

KMP算法查找串S中含串P的个数count

#include iostream

#include stdlib.h

#include vector

using namespace std;

inline void NEXT(const string T,vectorint next)

{

//按模式串生成vector,next(T.size())

next[0]=-1;

for(int i=1;iT.size();i++ ){

int j=next[i-1];

while(T!=T[j+1] j=0 )

j=next[j] ; //递推计算

if(T==T[j+1])next=j+1;

else next=0; //

}

}

inline string::size_type COUNT_KMP(const string S,

const string T)

{

//利用模式串T的next函数求T在主串S中的个数count的KMP算法

//其中T非空，

vectorint next(T.size());

NEXT(T,next);

string::size_type index,count=0;

for(index=0;indexS.size();++index){

int pos=0;

string::size_type iter=index;

while(posT.size() iterS.size()){

if(S[iter]==T[pos]){

++iter;++pos;

}

else{

if(pos==0)++iter;

else pos=next[pos-1]+1;

}

}//while end

if(pos==T.size()(iter-index)==T.size())++count;

} //for end

return count;

}

int main(int argc, char *argv[])

{

string S="abaabcacabaabcacabaabcacabaabcacabaabcac";

string T="ab";

string::size_type count=COUNT_KMP(S,T);

coutcountendl;

system("PAUSE");

return 0;

}

补上个Pascal的KMP算法源码

PROGRAM Impl_KMP;

USES

CRT;

CONST

MAX_STRLEN = 255;

VAR

next : array [ 1 .. MAX_STRLEN ] of integer;

str_s, str_t : string;

int_i : integer;

Procedure get_nexst( t : string );

Var

j, k : integer;

Begin

j := 1; k := 0;

while j Length(t) do

begin

if ( k = 0 ) or ( t[j] = t[k] ) then

begin

j := j + 1; k := k + 1;

next[j] := k;

end

else k := next[k];

end;

End;

Function index( s : string; t : string ) : integer;

Var

i, j : integer;

Begin

get_next(t);

index := 0;

i := 1; j := 1;

while ( i = Length(s) ) and ( j = Length(t) ) do

begin

if ( j = 0 ) or ( s = t[j] ) then

begin

i := i + 1; j := j + 1;

end

else j := next[j];

if j Length(t) then index := i - Length(t);

end;

End;

BEGIN

ClrScr;

Write(s = );

Readln(str_s);

Write(t = );

Readln(str_t);

int_i := index( str_s, str_t );

if int_i 0 then

begin

Writeln( Found , str_t, in , str_s, at , int_i, . );

end

else

Writeln( Cannot find , str_t, in , str_s, . );

END.

index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0

不再赘述算法原理，下面是两个函数，已经通过测试，可以直接用。

private int[] get_nextval(String t) {

int len = t.length();

int i = 0;

int j = -1;

int next[] = new int[len];

while (i len - 1) {

if (j == -1 || (t.charAt(i) == (t.charAt(j)))) {

i++;

j++;

if (t.charAt(i) != (t.charAt(j))) {

next[i] = (j + 1);

} else {

next[i] = next[j];

}

} else {

j = (next[j] - 1);

}

}

return next;

}

private int index_KMP(String s, String t, int[] next) {

int i = 0;

int j = 0;

while (i s.length() - 1 j t.length() - 1) {

if (j == 0 || (s.charAt(i) == t.charAt(j))) {

i++;

j++;

} else

j = (next[j] - 1);

}

if (j t.length() - 2) {

return (i - t.length() + 1);

} else

return -1;

}

如何java读取海量中文文本

使用Boyer-Moore算法

或者使用KMP算法

建议使用后者

KMP算法（java）

public class KMP {

/**

* @param args

*/

//计算模式串的next值

public static void getNext(String strModel, int dNext[]){

int i = 0,j = 1;

dNext[1] = 0;

while(j strModel.length()){

while(i 0 strModel.charAt(i) != strModel.charAt(j))//递推

i = dNext[i];

i++;

j++;

if(j == strModel.length())

break;

if(strModel.charAt(j) == strModel.charAt(i))//得出next值

dNext[j] = dNext[i] + 1;

else

dNext[j] = i;

}

}

//利用next值查询子串

public static int getSubString(String strMain, String strModel, int dStart){

int dPos = -1;

int i = dStart;

int j = 1;

int dNext[] = new int[200];

getNext(strModel, dNext);

while(istrMain.length()){

if(strMain.charAt(i) == strModel.charAt(j)){//当前字符匹配

if(j == (strModel.length()-1)){//查找成功

dPos = i - j + 1;

break;

}

i++;

j++;

}

else{//当前字符不匹配

if(dNext[j] == 0){

i++;

j = 1;

}

else{

j = dNext[j];

}

}

}

return dPos;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

String strModel = " jlsdjflskjdm";

int[] dNext = new int[20];

getNext(strModel, dNext);

for(int i = 1; istrModel.length(); i++)

System.out.print(dNext[i] + " ");

String strMain = " aaaaaaaaaaabbbcdabbksfjlsdjflskjd";

System.out.println();

System.out.println(getSubString(strMain, strModel, 1));

}

}

kmp算法详解

KMP模式匹配算法

KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。

求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。

include "string. h"

#includeassert. h

int KMPStrMatching(String T, String P, int. N, int startIndex)

{int lastIndex=T.strlen() -P.strlen();

if((1 astIndex- startIndex)0)//若 startIndex过大,则无法匹配成功

return (-1);//指向P内部字符的游标

int i;//指向T内部字符的游标

int j=0;//指向P内部字符的游标

for(i= startIndex; i T.strlen(); i++)

{while(P[j]!=T[i] j0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回该T子串的开始位置

}

return (-1);

}

数据结构与算法——字符串匹配问题(KMP算法)

KMP算法也是比较著名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：

T = “abcdex”

j 123456

模式串 abcdex

next[j] 011111

T = "abcabx"

j 123456

模式串T abcabx

next[j] 011123

T = "ababaaaba"

j———————123456789

模式串T——— ababaaaba

next[j]————011234223

T = "aaaaaaaab"

j———————123456789

模式串T——— aaaaaaaab

next[j]————012345678

next数组其实就是求解字符串要回溯的位置

假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};

在求解nextVal数组的5种情况