KMP

字符串类算法

寻找子串、寻找回文字符串（逆序之后寻找子串）

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void getNextArray(string &str, vector<int> &next)
{
    if (str.length() == 1)
    {
        next.push_back(-1);
        return;
    }
    next.resize(str.length());
    next[0] = -1;
    next[1] = 0;
    int i = 2; // next数组的位置
    int cn = 0;
    while (i < next.size())
    {
        if (str[i - 1] == str[cn])
        {
            next[i++] = ++cn;
        }
        // 当前跳到cn位置的字符，和i-1位置字符配不上
        else if (cn > 0)
        {
            cn = next[cn];
        }
        else
        {
            next[i++] = 0;
        }
    }
}
int KMP(string &s, string &m)
{
    if (m.length() < 1 || s.length() < m.length())
    {
        return -1;
    }
    int i1 = 0;
    int i2 = 0;
    vector<int> next;
    // O(M)
    getNextArray(m, next);
    // O(N)
    while (i1 < s.length() && i2 < m.length())
    {
        if (s[i1] == m[i2])
        {
            i1++;
            i2++;
        }
        // i2 == 0
        // i2来到0位置，只有0位置为-1
        else if (next[i2] == -1)
        {
            i1++;
        }
        else
        {
            i2 = next[i2];
        }
    }
    // i1越界或者i2越界了
    return i2 == m.length() ? i1 - i2 : -1;
}

void test1()
{
    string s = "abbztabbxabbg";
    string m = "abbg";
    cout << KMP(s, m) << endl;
}

int main()
{
    test1();
    
    return 0;
}