KMP算法2

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 int next[20];
 5 void getNext(char pattern[])
 6 {
 7     int k=-1,len=strlen(pattern),j=0;
 8     next[0]=-1;
 9     while(j<len){
10         if(k==-1||pattern[k]==pattern[j]){
11             k++;j++;
12             next[j]=k;
13         }else{
14             k=next[k];
15         }
16     }
17 }
18 
19 int KMP(char text[],char pattern[])
20 {
21     int i=0,j=0,lent=strlen(text),lenp=strlen(pattern);
22     getNext(pattern);
23     while(i<lent&&j<lenp){
24         if(j==-1||text[i]==pattern[j]){
25             i++;j++;
26         }else{
27             j=next[j];
28         }
29     }
30     if(j==lenp)
31         return i-j;
32     return -1;
33 }
34 
35 char* strSub(char* s,int pos,int length)//字符串截取函数
36 {
37     char *sub=(char *)calloc(length,sizeof(char));
38     int i=pos;
39     int count=0;
40     while(count<length)
41     {
42         sub[count]=s[i];
43         i++;
44         count++;
45     }
46     sub[count]='\0';
47     return sub;
48 }
49 
50 char* strReplace(char* s,char* sub,char* replaceStr)//字符串替换函数
51 {
52     int end;
53     char* temp1;
54     char* temp2;
55     int begin=0;
56     int subLength=strlen(sub);
57     end=KMP(s,sub);
58     while(end!=-1)
59     {
60         temp1=strSub(s,begin,end-begin);
61         temp2=strSub(s,end+subLength,strlen(s)-(end+subLength));
62         s=strcat(temp1,replaceStr);
63         s=strcat(s,temp2);
64         end=KMP(s,sub);
65     }
66     return s;
67 }
68 int main()
69 {
70     char s[100],sub[10],replaceStr[10];
71     char *answer=(char *)calloc(100,sizeof(char));
72     printf("input s:\n");
73     gets(s);
74     printf("input sub:\n");
75     gets(sub);
76     printf("input replaceStr:\n");
77     gets(replaceStr);
78     answer=strReplace(s,sub,replaceStr);
79     printf("final str is:\n");
80     puts(answer);
81     return 0;
82 }