KMP算法

[来源] 达内    [编辑] 达内   [时间]2012-09-14

C语言字符串匹配KMP算法的简单实现。

KMP算法

 

C 语言字符串匹配 KMP 算法的简单实现。

001 /*

 

002 KMP算法(C语言实现)
003 */
004
005
006 #include<stdio.h>
007 #include<string.h>
008
009
010 int *next=NULL; //存储子串的next值
011
012 void main()
013 {
014 int i=0,j=0;
015 int *ChildString( char *p );
016
017 char pristr[100]; //主串
018 char substr[100]; //子串
019 int nPristr=0; //主串长度
020 int nSubstr=0; //子串长度
021
022 printf("主串:"); //通过键盘输入两字符串
023 gets(pristr);
024 printf("子串:");
025 gets(substr);
026
027 nPristr=strlen(pristr); //求两字符串长度
028 nSubstr=strlen(substr);
029
030 next=malloc( sizeof(int *) * nSubstr ); //为next指针开辟空间
031 next=ChildString( &substr , nSubstr ); //调用函数计算数组各个元素的值
032
033 printf("\n子串next数组的值:\n");
034 for(i=0;i<nSubstr;i++)
035 {
036 printf("next[%d]= %d ",i,*(next+i));
037
038 if( (i+1)%3 == 0 )
039 printf("\n");
040 }
041
042
043 for( i=0,j=0 ; i<nPristr,j<nSubstr ; )
044 {
045 if( pristr[i]==substr[j] )
046 {
047 i++;
048 j++;
049 }
050 else
051 {
052 j=next[j];
053 if(j==-1)
054 {
055 i++;
056 j++;
057 }
058 }
059
060 if( j==nSubstr )
061 {
062 printf("\n\n匹配位置:%d\n",i-j+1);
063 break;
064 }
065 else if( i==nPristr )
066 {
067 printf("\n\n匹配位置:0\n");
068 break;
069 }
070 }
071 }
072
073
074 int *ChildString( char *p , int n ) //计算子串的next数组的各个元素值
075 {
076 int *c=NULL;
077 int i=0;
078 int j=0,k=0,flag=0;
079
080 c=malloc( sizeof(int *) * n );
081
082 *(c+0)=-1;
083 *(c+1)=0;
084
085 for(j=2;j<n;j++)
086 {
087 for(i=j-1;i>0;i--)
088 {
089 flag=1;
090
091 for(k=0;k<i;k++)
092 {
093 if( *(p+k) != *(p+j-i+k) )
094 {
095 flag=0;
096 break;
097 }
098 }
099
100 if(flag==1)
101 {
102 *(c+j)=i;
103 break;
104 }
105 else
106 *(c+j)=0;
107 }
108 }
109
110 return c;
111 }
 

资源下载