BF 算法总感觉写法怪怪的，改了一下

ZhaoYuBetter

欢迎拍砖哈，代码个数 可使用 codeblok 格式化一下：算法学起来比较吃力。。。:cry

#include <stdio.h>
#include <stdlib.h>

typedef char* String;

// 返回子串T在主串S中第pos个字符之后的位置
// 若不存在，则返回0
// T非空，1 <= pos <= strlen(S)
int index(String S, String T, int pos)
{
      int i = pos;
      int j = 0;
      int lenS = strlen(S);
      int lenT = strlen(T);

     while(i<lenS && j<lenT) {
      if(S[i] == T[j]) {      // 判断下一个
         i++;
          j++;
     } else {        // 回溯
        i = i-j+1;
        j = 0;
     }
    }

    if(j > lenT - 1) {
    return i - lenT;
    } else {
    return -1;
 }
}

int main()
{
    int i;
    i = index("Helloo", "lo", 0);
    printf("index: %d", i);
    return 0;
}

ZhaoYuBetter

一般编程语言，都是 返回 -1 表示匹配不到的意思。

ZhaoYuBetter

修改好的 KMP 算法：

#include <stdio.h>
#include <stdlib.h>

typedef char* String;


// KMP 算法start
/*
 获取 KMP 的 next 数组
*/
void getNext(String T, int *next)
{
    int j = -1;  // 前
    int i = 0;  // 后

    next[0] = -1;            // next数组第一个元素为-1
    int lenT = strlen(T);   // 字符串长度

    while( i < lenT)
    {
        // 刚开始or匹配相等加1向前走（BF原則）
        if(-1==j || T[i] == T[j])
        {
            j++;
            i++;
            if(T[i] != T[j])
            {
                next[i] = j;    // 填下一个
            }
            else
            {
                next[i] = next[j];
            }

        }
        else
        {
            j = next[j];
        }
    }
}

// 返回子串T在主串S第pos个字符之后的位置
// 若存在，返回-1
int indexKMP(String S, String T, int pos)
{
    int i = pos;
    int j = 0;
    int next[255];

    getNext(T, next);   // 获取next数组
    int lenS = strlen(S);
    int lenT = strlen(T);

    while(i<lenS && j<lenT)
    {
        if(-1 == j || S[i] == T[j]) //j=-1，没有这个元素，指向下一个元素，类似BF算法
        {
            i++;
            j++;
        }
        else            // 匹配失败
        {
            j = next[j];
        }
    }

    if(j > lenT - 1)
    {
        return i - lenT;
    }
    else
    {
        return -1;
    }


}


// KMP 算法end

int main()
{

    i =  indexKMP("ababaaabacca", "aaaa", 0);
    printf("KMP, index: %d ", i);
    printf("\n");
    return 0;
}

磨牙耗子

4#说的啥、