kmp算法程序C语言,KMP算法C语言程序实现

//

/*KMP算法*/

#include

#include

#include

using namespace std;

void getNext(char a[],int next[]){

int i,j;

next[1] &＃61; 0;

j &＃61; 0;

i &＃61; 2;

int m &＃61; strlen(a)-1; //从a[1]开始

while(i<&＃61;m){

if(a[j&＃43;1] &＃61;&＃61; a[i]){

j&＃43;&＃43;; next[i&＃43;&＃43;] &＃61; j;

}

else if(j&＃61;&＃61;0){

next[i&＃43;&＃43;] &＃61; 0;

}else if(j>0){

j &＃61; next[j];

}

}

}

int match(char a[],char b[],int next[]){

int i&＃61;0,j&＃61;0;

int pos;

int n &＃61; strlen(a)-1;

int m &＃61; strlen(b)-1;

while(1){

if(i>n) {

pos &＃61; -1; break;

}

if(j&＃61;&＃61;m){

//pos &＃61; i-j&＃43;1; break;

cout<

}

if(b[j&＃43;1] &＃61;&＃61; a[i&＃43;1] ){

j&＃43;&＃43;; i&＃43;&＃43;;

}else{

if(j&＃61;&＃61;0) i&＃43;&＃43;;

else if (j>0){

j &＃61; next[j];

}

}

}

}

/*

int main()

{

//char b[] &＃61; "!ababbc";

char b[] &＃61; "!abab";

int l &＃61; strlen(b);

int *next &＃61; new int[l-1];

getNext(b,next);

int i;

for(i&＃61;1;i<&＃61;l-1;i&＃43;&＃43;){

printf("%d ",next[i]);

}

cout<

char a[] &＃61; "!ababababbc";

int pos &＃61; match(a,b,next);

cout<

}

*/

//

/*

KMP应用&＃xff1a; 求一个串中所有前缀等于后缀的子串长度

*/

void output(int i,int next[]){

while(next[i]>0){

cout<

i &＃61; next[i];

}

}

/*

int main()

{

char b[] &＃61; "!ababa";

int l &＃61; strlen(b);

int *next &＃61; new int[l-1];

getNext(b,next);

int i;

for(i&＃61;1;i<&＃61;l-1;i&＃43;&＃43;){

printf("%d ",next[i]);

}

cout<

output(l-1,next);

delete[] next;

}

*/

标签&＃xff1a;

版权申明&＃xff1a;本站文章部分自网络&＃xff0c;如有侵权&＃xff0c;请联系&＃xff1a;west999com&＃64;outlook.com

特别注意&＃xff1a;本站所有转载文章言论不代表本站观点&＃xff01;

本站所提供的图片等素材&＃xff0c;版权归原作者所有&＃xff0c;如需使用&＃xff0c;请与原作者联系。