CF633C Spy Syndrome 2(ACAM简单应用)

LINK

随机数据下,时间复杂度应该是碾压哈希的hhh

大小写是不重要的,因为第一步总是会把大写改成小写

所以我们可以暂时把字符集的大小都变成小写去匹配

然后拿样例来说

iherehtolleh

我们匹配这个,其实可以把这个串反过来

hellotherehi

然后匹配这个玩意,最后把答案倒过来就好了

这个串匹配的结果就是

我们定义为匹配是否有可能

假如暴力枚举个字符复杂度上天

不妨对这个串建立自动机,暴力跳转移

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
string s[maxn];
char a[maxn],b[maxn];
int n,m,len[maxn],f[maxn],pre[maxn];
int ed[maxn],fail[maxn],zi[maxn][26],id;
void insert(int num)
{
    int l = len[num], now = 0;
    for(int i=0;i<l;i++)
    {
        int c = s[num][i]-'a';
        if( s[num][i]>='A'&&s[num][i]<='Z' )    c = s[num][i]-'A';
        if( !zi[now][c] )    zi[now][c] = ++id;
        now = zi[now][c];
    }
    ed[now] = num;
} 
void get_fail()
{
    queue<int>q;
    for(int i=0;i<=25;i++)    if( zi[0][i] )    q.push( zi[0][i] );
    while( !q.empty() )
    {
        int u = q.front(); q.pop();
        for(int i=0;i<=25;i++)
        {
            if( zi[u][i] )    fail[zi[u][i]] = zi[fail[u]][i],q.push( zi[u][i] );
            else    zi[u][i] = zi[fail[u]][i];
        }
    }
}
void dfs(int x)
{
    if( x==0 )    return;
    cout << s[pre[x]] << " ";
    dfs( x-len[pre[x]] );
}
int main()
{
    scanf("%d%s",&n,a+1);
    for(int i=1;i<=n;i++)    b[i] = a[n-i+1];
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin >> s[i]; len[i] = s[i].length();
        insert( i );
    }
    get_fail();
    f[0] = 1;
    int now = 0;
    for(int i=1;i<=n;i++)
    {
        now = zi[now][b[i]-'a'];
        for(int t=now;t;t=fail[t] )
        {
            if( ed[t]==0 )    continue;
            if( f[i-len[ed[t]]]==0 )    continue;
            f[i] = 1; pre[i] = ed[t];    
            break;
        }
    }
    dfs(n);
}