字符串匹配算法————数据结构复习复习

现复习BF算法及KMP算法
其他算法待
KMP思路理解推荐

#include 
#include 

using namespace std;

int BF(string s, string t);
//RK算法 待
void getNext(string t, int next[]);
int KMP(string s, string t, int next[]);
//BM算法 待
//Sunday算法 待
int main()
{
    string s = "acabaabcaabcacaabc";
    string t = "abaabc";
    int next[10];
    cout << BF(s,t);;
    cout << KMP(s, t, next);
    return 0;
}
int BF(string s, string t)
{//直接硬暴力
    int s_n = s.size(),t_n = t.size();     //获取字符串长度
    int s_p = 0, t_p = 0;                  //初始化
    while (s_p < s_n && t_p < t_n)         // 两指针均为循环限定
        if (s[s_p] == t[t_p])              //查到等
            s_p++,t_p++;                   //两指针均前进
        else
            s_p = s_p - t_p + 1,t_p = 0;   //两指针均复原
    if (t_p >= t_n)                        //短串走到头
        return s_p - t_p;                  //指针差值（长串对应指针头）
    else
        return -1;                         //未找到
}
void getNext(string t, int next[])
{//板子 更新next数组
    int n = t.size();                //获取字符串长度
    int i = 0, j = -1;               //初始化
    next[i] = j;                     //数组初始化
    while (i < n - 1)                // i为循环限定
        if (j == -1 || t[i] == t[j]) //查到头||查到等
            next[++i] = ++j;         // next只在此更新 i同
        else
            j = next[j];             // j往前查 下一循环判
}
//http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
int KMP(string s, string t, int next[])
{//板子 返回符合串开始的下标
    int s_n = s.size(), t_n = t.size();    //获取字符串长度
    int s_p = 0, t_p = 0;                  //初始化
    getNext(t, next);                      //数组初始化
    while (s_p < s_n && t_p < t_n)         // 两指针均为循环限定
        if (t_p == -1 || s[s_p] == t[t_p]) //查到头||查到等
            s_p++, t_p++;                  //长串指针只在此更新
        else
            t_p = next[t_p];               //短串往前查 下一个循环判
    if (t_p == t_n)                        //短串走到头
        return s_p - t_p;                  //指针差值（长串对应指针头）
    else
        return -1;                         //未找到
}