精易论坛

标题: KMP分享 [打印本页]
作者: shituo    时间: 2021-8-3 01:46
标题: KMP分享
  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. }

  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. }
复制代码


作者: haduke    时间: 2021-8-3 08:47
易论坛，你给我来个C？
作者: shj0205    时间: 2021-8-3 09:24
支持开源~！感谢分享
作者: 易神    时间: 2021-8-3 10:18
支持开源~！感谢分享
作者: tian89    时间: 2021-8-3 23:20
这个寻找是用C函数写的那里面是否越过\0也就结束符？易语言的寻找字节集可以越过去！我看了微软网站的C函数都是以结束符在判断终止寻找的！一旦字符串中间有结束符后边就寻找不到了
作者: 懒人定制软件    时间: 2021-8-5 01:04
这么厉害！必须给个红包鼓励下~
作者: ghost12    时间: 2022-1-24 00:01
我读书少，不要骗我
作者: ctry78985    时间: 2022-11-11 15:31
支持开源~！感谢分享
作者: 清风徐来2    时间: 2022-12-20 17:00
感谢分享



欢迎光临 精易论坛 (https://125.confly.eu.org/) Powered by Discuz! X3.4