4.36c.cpp

从输入的字符串中找到匹配字符串,修改也可以找到匹配的最长字符串

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int *FailFunction(short *str) 
{ 
int i, j, len; 
int *f; 

len = strlen((char *)str)/2; 
f = (int *)malloc(len*sizeof(int)); 
if(f == NULL) 
{ 
printf("Allocate memory fail!\n"); 
exit(1); 
} 

f[0] = -1; 
for(j=1; j<len; j++) 
{ 
i = f[j-1]; 
while((*(str+j) != *(str+i+1)) && (i >= 0)) 
i = f[i]; 
if(*(str+j) == *(str+i+1)) 
f[j] = i+1; 
else 
f[j] = -1; 
} 

return f; 
} 
 
char *FindStr(short *pSour, short *pFind) 
{ 
int posF=0, posS=0; 
int lengthF, lengthS; 
int *fail; 

fail = FailFunction(pFind); 
lengthF = strlen((char *)pFind)/2; 
lengthS = strlen((char *)pSour)/2; 
while(posF < lengthF && posS < lengthS) 
{ 
if(pFind[posF] == pSour[posS]) 
{ 
posF++; 
posS++; 
} 
else if(posF == 0) 
posS++; 
else 
posF = fail[posF-1]+1; 
} 

free(fail); 
if(posF < lengthF) 
return NULL; 
else 
return (char *)(pSour+(posS-lengthF)); 
} 
//main函数省略！