洛谷 P3796 【模板】AC 自动机（加强版）题解

· · 个人记录

P3796 【模板】AC 自动机（加强版）

原题链接

题意简述

很清晰，就不简述了

题目分析

这是一篇哈希做法的题解（update：作者对复杂度的分析就像依托答辩，欢迎指出错误qaq）

个人觉得这题还有提交哈希题解的必要，因为在一定数据范围之内的情况下哈希写法的行数更短且比较容易理解，小压一下可以压到AC自动机 2/3 的行数。

首先说一下用哈希匹配多个模式串的做法。

如果是暴力来搞，那么对于一个字符串，就先哈希出来，然后 O(n) 枚举起点，再进行比较，但这样的复杂度貌似是 O(N|T|) 的，跑不过我没逝过。

为了保险起见，我们肯定还想再优化优化。

考虑预处理出文本串中相邻 n 个字母的映射，比如说一个文本串aweroiioaegrwdvfnbj，我们开两个指针 i,j，每移动一次向这两个字母对应的 vector 压入一个 i 表示起点，比如当前 i = 1,j = 2，则我们进行如下操作：

vector<int> m[26][26]; //最多可以开到四维
char s[maxn];
//.......
m[s[i] - 'a'][s[j] - 'a'].push_back(i);

然后对于每个模式串，我们只枚举其开头两个字母对应的起点即可，无需从头到尾枚举。

注意如果模式串长度为 1 的话枚举即可，或另开一个数组记录起点。

这样的话时间复杂度貌似可以压到 O(N|T|/26/26)，当然也可以开三维的，跑的能更快些。

代码实现

#include <bits/stdc++.h>
#define maxn 1001000
#define SEED 13331
#define re register
using namespace std;
typedef unsigned long long ull;
char target[maxn], str[151][71];  // 文本串和模式串数组
ull p[maxn], sum1[maxn], sum[151][71];  // 进制数组、文本串hash数组、模式串哈希数组
vector<int> m[26][26], ans;  // 匹配
inline ull calc1(int l,int r){return sum1[r] - sum1[l - 1] * p[r - l + 1];}  // 计算文本串哈希，模式串哈希直接sum[i][slen[i]]即可
int n, num, tlen, slen[151], ma;  // slen表示模式串长度数组

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    p[0] = 1;
    for(re int i = 1; i < maxn; i++) p[i] = p[i - 1] * SEED;  // 预处理
    while(cin >> n && n){
        ma = 0, ans.clear();  // 答案vector清空
        for(re int i = 1; i <= n; i++) cin >> (str[i] + 1), slen[i] = strlen(str[i] + 1);
        for(re int i = 1; i <= n; i++) for(int j = 1; j <= slen[i]; j++) sum[i][j] = sum[i][j - 1] * SEED + str[i][j] - 'a';  // 读入 + 预处理
        cin >> (target + 1);
        tlen = strlen(target + 1);
        for(re int i = 1; i <= tlen; i++) sum1[i] = sum1[i - 1] * SEED + target[i] - 'a';
        for(re int i = 0; i < 26; i++) for(int j = 0; j < 26; j++) m[i][j].clear();  // 二层循环初始化一下
        for(re int i = 1,j = 2; j <= tlen; j++, i++) m[target[i] - 'a'][target[j] - 'a'].push_back(i);  // 预处理一下
        for(re int i = 1; i <= n; i++){
            num = 0;
            if(slen[i] == 1){  // 特判
                for(re int j = 1; j <= tlen; j++) if(target[j] == str[i][1]) num++;
                if(num == ma) ans.push_back(i);
                else if(num > ma) ma = num, ans.clear(), ans.push_back(i);
                continue;
            }
            if(m[str[i][1] - 'a'][str[i][2] - 'a'].size() == 0) continue;
            int l = str[i][1] - 'a', r = str[i][2] - 'a';
            for(re int u = 0; u < m[l][r].size(); u++){
                int st = m[l][r][u]; //枚举起点
                if(calc1(st, st + slen[i] - 1) == sum[i][slen[i]]){num++;}  // 匹配到了，退出，不然下一个
            }
            if(num == ma) ans.push_back(i);
            else if(num > ma) ma = num, ans.clear(), ans.push_back(i);
        }
        cout << ma << '\n';
        for(re int i = 0; i < ans.size(); i++){  // 输出答案
            for(re int j = 1; j <= slen[ans[i]]; j++) cout << str[ans[i]][j];
            cout << '\n';
        }
    }
    return 0;
}

后排提示：二次加强版这种哈希做法通过不了，如果有哈希艹过的欢迎发一下做法 /bx