kmp算法java代码,kmp算法 csdn

如何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算法的C语言实现2007-12-10 23:33

基本思想：

这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。

其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

#include stdio.h

#include string.h

int index_KMP(char *s,char *t,int pos);

void get_next(char *t,int *);

char s[10]="abcacbcba";

char t[4]="bca";

int next[4];

int pos=0;

int main()

{

int n;

get_next(t,next);

n=index_KMP(s,t,pos);

printf("%d",n);

return 0;

}

int index_KMP(char *s,char *t,int pos)

{

int i=pos,j=1;

while (i=(int)strlen(s)j=(int)strlen(t))

{

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

{

i++;

j++;

}

else j=next[j];

}

if (j(int)strlen(t))

return i-strlen(t)+1;

else

return 0;

}

void get_next(char *t,int *next)

{

int i=1,j=0;

next[0]=next[1]=0;

while (i(int)strlen(t))

{

if (j==0||t[i]==t[j])

{

i++;

j++;

next[i]=j;

}

else j=next[j];

}

}

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;

}

急！kmp算法代码

LZ的get_next函数和Index_KMP函数的代码是复制粘贴的吧，那对应的是字符数组下标以1开始的代码，此外也有少量错误，修改后的正确代码如下。另外，LZ的代码中找不到next数组的定义，并且元素类型应该int才对头，这点需要在适当位置补充。

void get_next(HString T, int *next)

{

int i=0, j=-1;

next[0] = -1;     ///// 关键

while(i  T.length-1) 

{

if (j==-1 || T.ch[i]==T.ch[j])

{

++i;

++j;

////////////// 改进版 KMP 增加此判断 /////////

if (T.ch[i]==T.ch[j])

next[i]==next[j];

else

////////////////////////////////////////////

next[i]==j;

}

else

j = next[j];

}

}

int Index_KMP(HString S, HString T, int pos)

{

int i=pos, j=0;

get_next(T, next);

while(iS.length  jT.length)

{

if(j==-1 || S.ch[i]==T.ch[j])

{

++i;

++j;

}

else

j = next[j];

}

if(j=T.length)

return i-T.length;  // 返回的匹配位置从下标 0 起算

else

return -1;      // 返回 -1 表示没有找到

}