Knuth-Morris-Pratt算法

KMP算法：这是未经优化的版本。

/*

 *knuth,morris,pratt模式匹配算法

 *程序在字符串string中找出pat字符串第一次出现的位置

 *match和compute_prefix_function的总体时间为：O(strlen(string)+strlen(pat))

 */

#include

#include

#define MAX_STRING_SIZE 100

#define MAX_PATTERN_SIZE 100

int match();

void fail();

int failure[MAX_PATTERN_SIZE];//

char string[MAX_PATTERN_SIZE];//目标字符串

char pat[MAX_PATTERN_SIZE];//要匹配的字符串

/*匹配函数：*/

int match(char *string,char *pat)

{

int i=0,j=0;

int lens=strlen(string);

int lenp=strlen(pat);

while(i

{

if(string[i]==pat[j])

{

j++;

i++;

}

else

{

if(j)

{

j=failure[j-1];

}

else

{

i++;

}

}

}

return (j==lenp)?i-lenp:-1;

}

/*失配函数：f(j)=max(i,0),若存在p0p1...pi = pj-ipj-i+1...pj ,i

 *          f(j)=-1       否则。

*/

void compute_prefix_function(char *pat)

{

int j=0,i=1;

failure[0]=0;

while(i

{

if(pat[j]==pat[i])

{

i++;

j++;

failure[i-1]=j;

}

else

{

i++;

failure[i-1]=0;

j=0;

}

}

}

/*main*/

int main()

{

int n;

char string[MAX_PATTERN_SIZE]="bacbababaababababcaabcbab";

char pat[MAX_PATTERN_SIZE]="ababababca";

compute_prefix_function(pat);

n=match(string,pat);

printf("%d",n);

}

阅读(2401) | 评论(0) | 转发(0) |

0

上一篇：牛人博客/网站

下一篇：线程