KMP分享

shituo

1. void kmp_init(const char *s, int *prefix, size_t size) {
   
2.     prefix[0] = 0;
   
3.     for (size_t i = 1; i < size; ++i) {
   
4.         if (s[i] == s[prefix[i - 1]])
   
5.             prefix[i] = prefix[i - 1] + 1;
   
6.         else {
   
7.             int j = i - 1;
   
8.             while (prefix[j] > 0 && s[prefix[j]] != s[i])
   
9.                 j = prefix[j] - 1;
   
10.             if (prefix[j] > 0)
    
11.                 prefix[i] = prefix[j] + 1;
    
12.             else {
    
13.                 prefix[i] = (s[i] == s[0]);
    
14.             }
    
15.         }
    
16.     }
    
17. }
    
18. 
    
19. int strStr(const char *src, const char *dest) {
    
20.     if (!dest || !src)
    
21.         return -1;
    
22.     if (!*dest)
    
23.         return 0;
    
24.     size_t size = strlen(dest);
    
25.     int *prefix = malloc(sizeof(int) * size);
    
26.     kmp_init(dest, prefix, size);
    
27.     size_t i, j;
    
28.     for (i = j = 0; src[i] && j < size; ++i) {
    
29.         if (dest[j] == src[i]) {
    
30.             ++j;
    
31.         }
    
32.         else if (j) {
    
33.             while (prefix[j - 1] > 0 && dest[prefix[j - 1]] != src[i])
    
34.                 j = prefix[j - 1];
    
35.             if (prefix[j - 1] > 0) {
    
36.                 j = prefix[j - 1] + 1;
    
37.             }
    
38.             else {
    
39.                 j = (dest[0] == src[i]);
    
40.             }
    
41.         }
    
42.     }
    
43.     free(prefix);
    
44.     if (j < size)
    
45.         return -1;
    
46.     return i - size;
    
47. }

复制代码

清风徐来2

感谢分享

ctry78985

支持开源~！感谢分享

ghost12

我读书少，不要骗我

懒人定制软件

这么厉害！必须给个红包鼓励下~

tian89

这个寻找是用C函数写的那里面是否越过\0也就结束符？易语言的寻找字节集可以越过去！我看了微软网站的C函数都是以结束符在判断终止寻找的！一旦字符串中间有结束符后边就寻找不到了

易神

支持开源~！感谢分享

shj0205

支持开源~！感谢分享

haduke

易论坛，你给我来个C？