串的模式匹配 – 超越线性时间寻找子串

暴力匹配

模式串从头到尾推进，匹配时从左向右匹配，匹配失败时向前推进一个字符

int BrutalForce(string p, string s)
{
    int M = p.length();
    int N = s.length();
    for (int i = 0; i <= N - M; i++)
    {
        int j;
        for (j = 0; j < M; j++)
            if (s[i + j] != p[j])
                break;
        if (j == M) return i;
    }
    return N;
}

KMP算法

模式串从头到尾推进，匹配时从左向右匹配，匹配失败时跳步，可达O(N+M)

暴力匹配失败时会将指针回退到模式串初始位置，KMP算法依据已匹配部分进行跳步避免指针回退

匹配进行到失败字符fail时，若fail在模式串中，则将fail对准

若fail不在模式串中，含有fail的子串均无法匹配，直接将模式串对准fail字符的下一个字符

DFA版本

将字符位置看作状态，字符串匹配可看作有穷状态机的状态转移

DFA数组构建状态转移表，构建表和匹配时，匹配成功进入下一个状态，匹配失败回退到某个状态

    int KMP(string s, string p)
    {
        int M = p.length();
        int N = s.length();
        int R = 128;
        int DFA[R][M];

        memset(DFA, 0, sizeof(DFA));
        DFA[p[0]][0] = 1;
        for(int state = 1, pre = 0; state < M; state++)
        {
            for(int loca = 0; loca < R; loca++)
                DFA[loca][state] = DFA[loca][pre];
            DFA[p[state]][state] = state + 1;
            pre = DFA[p[state]][pre];
        }

        int i = 0, state = 0;
        for(; i < N && state < M; i++)
            state = DFA[s[i]][i];
        if(state == M) return i - M;
        return N;
    }

Boyer-Moore

模式串从头到尾推进，匹配时从右向左匹配，匹配失败则推进模式串跳步，可达O(N/M)

Boyer-Moore匹配成功时无需计算跳步值直接返回索引

每轮比较的首个匹配失败字符fail若在模式串中，直接将模式串中最右侧fail字符对齐字符串中的fail

若上述情况导致模式串向左倒退，直接将模式串向右推进一个字符

若fail若不在模式串中，则含有fail的子串均无法匹配，直接将模式串左侧对齐fail的下一个字符

int BoyerMoore(string s, string p)
{
    int M = p.length();
    int N = s.length();
    int R = 128;
    int r[R];
    int skip;

    memset(r, -1, sizeof(r));
    for (int i = 0; i < M; i++)
        r[p[i]] = i;

    for (int i = 0; i <= N - M; i += skip)
    {
        skip = 0;
        for (int j = M - 1; j >= 0; j--)
            if (s[i + j] != p[j])
            {
                skip = j - r[s[i + j]];
                if (skip < 1) skip = 1;
                break;
            }
        if (skip == 0) return i;
    }
    return N;
}

Rabin-Karp

计算模式串和等长子串的哈希值并比较，哈希值不同一定不匹配再推进重复，使用BKDR需O(nm)时间

哈希值相同的两字符串为相同串或哈希冲突，为保证正确性此时逐位比较字符串，实际冲突可能性极小无需再次比较

Rabin-Karp在前一串哈希值基础上计算当前串哈希值，可达线性复杂度

int size;
int hex;

long BKDRhash(string s, int len)
{
    long hash = 0;
    for(int i = 0; i < len; i++)
        hash = (hash * hex + s[i]) % size;
    return hash;
}

int RabinKarp(string s, string p)
{
    int M = p.length();
    int N = s.length();
    long pHash = BKDRhash(p, M);
    long sHash = BKDRhash(s.substr(0, M), M);

    for(int i = 0; i <= N - M; i++)
        if(pHash == sHash) return BrutalForce(s.substr(i, M), p);
        else if(i != N - M) sHash = ((sHash - s[i] * pow(hex, M - 1)) * hex + s[i + 1]) % size;

    return N;
}

AC自动机

预处理模式串生成状态表，根据读入的字符跳转状态，可进行多维字符串匹配