您的位置: 首页  >  IT文章  >  Linux GCC下strstr的实现以及一个简单的Kmp算法的接口

Linux GCC下strstr的实现以及一个简单的Kmp算法的接口

分类: IT文章 • 2024-02-29 15:46:01

今天做了一道题，要用判断一个字符串是否是另一个字符串的子串，于是查了一下strstr的实现。

代码如下：

 1 char *strstr(const char*s1,const char*s2)
 2 {
 3     const char*p=s1;
 4     const size_t len=strlen(s2);
 5     for(;(p=strchr(p,*s2))!=0;p++)
 6     {
 7         if(strncmp(p,s2,len)==0)
 8             return (char*)p;
 9     }
10     return(0);
11 }

从上面的GCC中strstr实现代码可以分析出，strstr的时间复杂度是O(n2)的(因为strncmp是O(N)的)，不过对长字符串匹配子串上可以采用kmp算法来提高效率（时间复杂度为O(m+n)），这里翻出了自己以前写的kmp算法的接口放到这里和大家分享一下，之前我也写过一篇关于kmp匹配子串的一篇文章，也可以去看一下。

这是我之前写的关于kmp介绍的文章地址:http://www.cnblogs.com/daimadebanyungong/p/4756853.html

下面是我翻出来的很早之前写的一个C版本的kmp算法的实现接口，欢迎纠正错误和分享经验。

  1 #include <string.h>
  2 #include <stdio.h>
  3 
  4 #define LIB_MATCH_NUM  5
  5 #define LIB_STRING_LEN 40
  6 
  7 char lib_match[LIB_MATCH_NUM][LIB_STRING_LEN] =
  8 {
  9     "www.baidu.comw",
 10     "www.google.com",
 11     "www",
 12     "baidu.com",
 13     "lualu",
 14 };
 15 
 16 int lib_match_len[LIB_MATCH_NUM];
 17 
 18 int lib_match_next[LIB_MATCH_NUM][LIB_STRING_LEN + 1] = {0};
 19 
 20 
 21 void get_next();
 22 
 23 void lib_match_init()
 24 {
 25     memset(lib_match_len,0,sizeof(lib_match_len));
 26     int i;
 27     for(i = 0; i < LIB_MATCH_NUM; i++)
 28     {
 29         lib_match_len[i] = strlen(lib_match[i]); 
 30     }
 31 
 32     get_next(); // init next array 
 33 }
 34 
 35 void get_next()
 36 {
 37     int i,j,k;
 38 
 39     for(i = 0; i < LIB_MATCH_NUM; i++)
 40     {
 41         
 42         lib_match_next[i][0] = 0;
 43         lib_match_next[i][1] = 0;
 44         
 45         k = 0; //point to the last next[j]
 46         int len = lib_match_len[i];
 47 
 48         for( j = 1; j < len; j++)
 49         {//j start from 1 because next start from 2
 50             k = lib_match_next[i][j]; //k = next[j];
 51             
 52             while(k > 0 && lib_match[i][j] != lib_match[i][k])
 53             {
 54                 k = lib_match_next[i][k];
 55             }
 56 
 57             if(lib_match[i][j] == lib_match[i][k])
 58             {//s[j] == s[next[k]] next[i+1] = next[k] +1
 59                 k++; 
 60             }
 61 
 62             lib_match_next[i][j+1] = k;
 63         }
 64     
 65     }
 66 
 67 }
 68 
 69 int lib_search(char *orignal,int len)
 70 {
 71     if(orignal == NULL)
 72     {
 73         return 0;
 74     }
 75 
 76     int i,j,k;
 77     
 78     for(i = 0; i < LIB_MATCH_NUM; i++)
 79     {
 80         char *tmp = orignal; // match each model need to start from the first
 81         k = 0; // k start from the last next array
 82 
 83         for(j = 0; j < len; j++)
 84         {
 85             
 86             while( k > 0 && tmp[j] != lib_match[i][k])
 87             {
 88                 k = lib_match_next[i][k];
 89             }
 90 
 91             if(tmp[j] == lib_match[i][k])
 92             {
 93                 k++;
 94             }
 95 
 96             if(k == lib_match_len[i])
 97             {
 98                 printf("match the model string %d : %s
", i,lib_match[i]);
 99                 printf("match at the position  :%d

", j - lib_match_len[i] + 1);
100                 
101                 // here can return the i to know which model string have been matched
102             
103                 k = lib_match_next[i][k]; //to match another this model string 
104             }
105 
106         }
107 
108     }    
109 
110     return 0;
111 }
112 
113 void print_next()
114 {
115     int i,j;
116     
117     for(i = 0; i < LIB_MATCH_NUM; i++)
118     {
119         printf("model string : %s 
",lib_match[i]);
120         printf("next array:");
121         for(j = 0; j < lib_match_len[i]+1;j++)
122         {
123             printf(" %d",lib_match_next[i][j]);
124         }
125         printf("

");
126     }
127 }
128 
129 
130 int main()
131 {
132     char orignal[40];
133         
134     lib_match_init();
135 
136     print_next();
137 
138     while(1)
139     {    
140 
141         scanf("%s",orignal);
142 
143         if(strcmp(orignal,"0") == 0)
144         {
145             return 0;
146         }
147 
148         lib_search(orignal,strlen(orignal));
149     }
150 
151     return 0;
152 
153 }

相关推荐