字符串匹配

字符串匹配

1. kmp算法

核心是对next数组的构建。
next[j]表示，在B[0]-B[j]所组成的这个子串中最长公共真前后缀的长度为x，通俗地说，若next[j]的值为x，则说明这个（B[0]-B[j]所组成的）子串的前x个字符和后x个字符相同。

时间复杂度为$O(n+m)$

#include <bits/stdc++.h>

const int MAXN=1e5;

char s[MAXN],t[MAXN];//s是模式串，t是被匹配串 
int nxt[MAXN];

void kmp(char s[],char t[]){

    int n=strlen(s),m=strlen(t);
    int j;
    for(int i=1;i<n;i++){
            int j=nxt[i-1];
        while(j&&s[i]!=s[j]){
                j=nxt[j-1];
        }//递推思维找nxt[i]
        if(s[i]==s[j]){
            nxt[i]=j+1;
        }else{
            nxt[i]=0;
        }
    }
    
    for(int i=0,j=0;i<m;i++){
        while(j&&t[i]!=s[j]){
            j=nxt[j-1];
        }
        if(t[i]==s[j]){
            j++;
        }
        if (j == n)
        {
            int ans = i - j + 1;
            j = nxt[j-1];//匹配成功 
        }
    }
}

2. 有限自动机匹配

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>

using namespace std;

bool Matching_Prefix_Suffix(char* P,int k,int q,char c)
{                               //P为模式串 K为要验证的前缀和后缀的字符串长度
    if(k==0)                    //q为当前自动机主线长度
    return true;              //k=0 空字符串 前缀和后缀肯定相等
    if(k==1){                //只有一个字符串 证明自动机刚好开始创建
        return P[0]==c;      //如果模式串的第一个和其中的c相等 前缀等于后缀
    }
    return P[k-1]==c&& (!strncmp(P,P+q-k+1,k-1));    //检验P[0...k-1]==P[q-k+1...q]
}
 
vector<map<char,int> > Compute_Transition_Function( char *P,const char* input_character)
{                                //计算转移函数的值
    int m=strlen(P);                //模式串的长度
    int j=0,k;
    printf("The main length of Finite_Automaton_Matcher is %d\n",m);
    vector<map<char,int> >transition_map(m+1);         //创建一个vector 一共有m+1个数据
    for(int i=0;i<m;i++){                   //对于模式串的长度
        j=0;
        while(input_character[j]!='\0'){      //对于输入串的每一种可能字符
         k= min(m+1,i+2);               //因为对于长度为i的字符串 它的转移函数最大值为i
        do{                          //数组下标从0开始 再加上后面k一来就减1  所以为i+2
            k=k-1;                  //找到一个最大值k使得模式串的P[0...k]==P[...n-1]
    }while(!Matching_Prefix_Suffix(P,k,i,input_character[j]));
        transition_map[i][input_character[j]]=k;
        j++;
        }
    }
    return  transition_map;           //返回一个vector 每一个元素为 map<char,int>
}                                     //char 为自动机中的字符 int 为转移函数值
 
void Finite_Automaton_Matcher(char* T,char* P,vector<map<char,int> >transition_map)
{
    int n=strlen(T);                           //文本串长度
    int m=strlen(P);                           //模式串长度
    int q=0;                                   //转移函数的值
     for(int i=0;i<n;i++){                    //对于文本串中的每一个字符
     q = transition_map[q][T[i]];             //迭代 前一个字符的转移函数值
     if(q==m)                                //转移函数的值等于模式串的长度
     printf("Pattern occurs with shift %d\n",i+1-m);   //模式串的有效位移为i-m+1
    }
}

int main()
{
    const char* input_character="abc";        //输入字母表
    char T[]="abababacaba";                  //文本串
    char P[]="ababaca";                      //模式串
    vector<map<char,int> >transition_map=Compute_Transition_Function(P,input_character);
    Finite_Automaton_Matcher(T,P,transition_map);
    return 0;
}

3. 哈希匹配法

#include <iostream>
#include <string.h>

using namespace std;

#define BASE 256
#define MODULUS 101

void RabinKarp(char t[], char p[])
{
    int t_len = strlen(t);
    int p_len = strlen(p);

    // 哈希滚动之用
    int h = 1;
    for (int i = 0; i < p_len - 1; i++)
        h = (h * BASE) % MODULUS;

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++)
    {
        t_hash = (BASE * t_hash + t[i]) % MODULUS;
        p_hash = (BASE * p_hash + p[i]) % MODULUS;
    }

    int i = 0;
    while (i <= t_len - p_len)
    {
         // 考虑到哈希碰撞的可能性，还需要用 memcmp 再比对一下
        if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
            cout << p << " is found at index " << i << endl;

        // 前缀和思想
        t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;

        // 防止出现负数
        if (t_hash < 0)
            t_hash = t_hash + MODULUS;

        i++;
    }
}

int main()
{
    char t[100] = "It is a test, but not just a test";
    char p[10] = "test";

    RabinKarp(t, p);

    return 0;
}

快速幂

ll fast_pow_mod(ll a, ll b, ll m){
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}