KMP 马拉车 算法的实现

更加精简的算法

#include<iostream>
#include<vector>
#include<algorithm>
#include<random>
#include<math.h>
using namespace std;

int KMP(string S, string T){
    // 求解 next 数组
    // 当前位置   前一个的 next 值
    int m = S.size(), n = T.size(), cur = 0, pre = -1;
    vector<int> next(n+1);
    next[0] = -1;
    while (cur < n) {
        if (pre == -1 || T[cur] == T[pre]) 
            next[++cur] = ++pre;
        else pre = next[pre];
    }

    // 两个字符串的下标
    int i = 0, j = 0;
    while(i < m && j < n){
        if(j == -1 || S[i] == T[j]) i++, j++;
        else j = next[j];
    }
    return j == n ? i - j : -1;
}

int getIndexOf(string S, string T){
    // 求解 T 是否为 S 的子串，若不是返回 -1   若是，返回起始下标
    if (T.size() > 0 && S.size() >= T.size() ) return KMP(S, T);
    else return -1;
}

string Manarcher(string p){
    // 马拉车算法， 求最长回文子串
    if(p.size() < 1) return 0;
    // 字符串预处理
    string str = "#";
    for(auto it:p) str = str + it + "#";

    // 回文半径辅助数组
    int arr[str.size()] = {0};
    // 最长回文中心  最长回文长度   当前回文中心   到达最右位置
    int max_c = 0, max_l = 0, cur_c = 0, cur_r = 0;
    for(int i=0; i<str.size(); i++){
        // 判断是否在区域里
        arr[i] = cur_r > i ? min(arr[2*cur_c - i], cur_r - i) : 0 ;
        while( i-arr[i]-1 >=0 && i+arr[i]+1 <= str.size() && str[i-arr[i]-1] == str[i+arr[i]+1] ) 
            arr[i]++;
        // 更新当前最大和最远
        cur_r < i + arr[i] ? cur_r = (cur_c = i) + arr[i] : 0;
        max_l < arr[i] ? max_l = arr[i], max_c = i : 0;
    }
    // max_l 为处理后字符串的半径， 即为原字符串的长度
    return p.substr((max_c - max_l)/2, max_l);
}




int main(){
    string S = "dfasaf", T = "asaf";
    int res = KMP(S, T);
    cout << res << endl;


    return 0;
}

#include<iostream>
#include<vector>
#include<math.h>
#include<sstream>
using namespace std;

int KMP(string& S, string& T){
    int len = T.size();
    // 求解 next 数组
    int next[len];
    next[0] = -1, next[1] = 0;
    // 当前位置   前一个的 next 值
    int cur = 2, pre = 0;
    while(cur < T.size()){
        if(T[cur-1] == T[pre]) next[cur++] = ++pre;
        else if(pre > 0) pre = next[pre];
        else next[cur++] = 0;
    }

    // 两个字符串的下标
    int Si = 0, Sj = 0;
    while(Si < S.size() && Sj < T.size()){
        if(S[Si] == T[Sj]) Si++, Sj++;
        else if(next[Sj] == -1) Si++;
        else Sj = next[Sj];
    }
    return Sj == T.size() ? Si - Sj : -1;
}

int getIndexOf(string& S, string& T){
    // 求解 T 是否为 S 的子串，若不是返回 -1   若是，返回起始下标
    if (T.size() > 0 && S.size() >= T.size() ) return KMP(S, T);
    else return -1;
}

int main(){
    string S,T;
    while(getline(cin, S)){
        getline(cin, T);
        vector<string> arr;
        string tem;
        stringstream ss(T);
        while(ss>>tem) arr.push_back(tem);
        bool flag = true;
        for(int i=0; i<arr.size(); i++)
            if(getIndexOf(S, arr[i]) == -1){
                cout<<"False"<<endl;
                flag = false;
                break;
            }
        if(flag) cout<<"True"<<endl;
    }
    return 0;
}