KMP算法(蛮力法)

浏览数：28 / 时间：2015年06月08日 
 1 #include<stdlib.h>
 2 #include<stdio.h>
 3 void next(char T[],int nextArr[],int n);
 4 
 5 int match(char S[],int tn,char T[],int sn,int nextArr[]);
 6 
 7 int main(void){
 8     char S[]="adefdfeeeeeeeeeabcdefgabcdefgaeiohxohoalslhoe";
 9     char T[]="abcdefgabcdefg";
10     int nextArr[14]={0};
11     int n=14;
12 
13     next(T,nextArr,n);
14 
15 //    int i=0;
16 //    for(;i<n;i++){
17 //        printf("%d ",nextArr[i]);
18 //    }
19 
20     int result = match(S,strlen(S),T,strlen(T),nextArr);
21     printf("%d",result);
22 
23 
24     return EXIT_SUCCESS;
25 }
26 
27 void next(char T[],int next[],int n){
28     next[0]=0;
29     int k=0,j=1;
30     while(j<n){
31         if((k==0||T[k]==T[j])){
32             next[j]=k;
33             k++;
34             j++;
35         }else{
36             k=next[k];
37         }
38     }
39 }
40 
41 int match(char S[],int tn,char T[],int sn,int nextArr[]){
42     int i=0,j=0;
43     int result=0;
44     for(;i<tn-sn+1;i++,j++){
45         if(S[i]==T[j]){
46             if(j==sn-1){
47                 result=1;
48                 break;
49             }
50             continue;
51         }else{
52             j=nextArr[j];
53         }
54     }
55     return result;
56 }

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢