Liveddd's Blog

愛にできることはまだあるかい

CF1801G A task for substrings

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 9 分钟

串串题。

$f_i$ 表示 $t[1,i]$ 有多少个后缀是单词，$g_i$ 表示 $t[1,i]$ 有最长的为单词的后缀的编号，$sum_i=\sum_{i=1}^i f_i$。尝试用 $sum_r-sum_{l-1}$ 计算答案。但是发现左端点在 $[1,l-1]$，右端点在 $[l,r]$ 的出现过的单词被多算了，我们需要重新考虑之一部分的贡献。

设 $cnt_{i,j}$ 表示编号为 $i$ 的单词长度为 $j$ 的后缀中出现了多少个单词吗，其状态数为 $\mathcal O(S)$。我们尝试找到最大的 $p$，满足 $p-|s_{g_p}|+1< l$。那么答案就等于 $sum_r-sum_p$，再加上 $[l,p]$ 对应的单词的后缀中出现的单词总数 $cnt_{g_p,p-l+1}$。

我们通过建正串 ACAM 容易处理出 $f_i,g_i$，建反串 ACAM 处理出 $cnt_{i,j}$。然后在线段树上二分求出 $p$。最终时间复杂度为 $\mathcal O(S+T+m\log T)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long 
using namespace std;
const int N=5e5+10,S=1e6+10,T=5e6+10,C=26,INF=1e9;
template <class T>
inline void read(T &x)
{
	x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
char s[S],t[T];
string rev[N];
int sl[N],tl;
int g[T];
ll sum[T];
vector<ll>f[N];

struct ACAM
{
    int tot,tr[S][C],fail[S],p[S],ed[S];
    void insert(int id,char *s)
    {
        int u=0,len=strlen(s);
        for(int i=0;i<len;i++)
        {
            if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
            u=tr[u][s[i]-'a'];
        }
        p[u]=id,ed[u]=1;
    }
    void build()
    {
        queue<int>q;
        for(int i=0;i<C;i++)if(tr[0][i])q.push(tr[0][i]);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            ed[u]+=ed[fail[u]];
            if(!p[u])p[u]=p[fail[u]];
            for(int i=0;i<C;i++)
            {
                if(tr[u][i])fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
                else tr[u][i]=tr[fail[u]][i];
            }
        }
    }
}AC1,AC2;

int val[T<<2];
void pushup(int x){val[x]=min(val[x<<1],val[x<<1|1]);}
void build(int x,int l,int r)
{
    if(l==r)
    {
        if(g[l])val[x]=l-sl[g[l]]+1;
        else val[x]=INF;
        return ;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    pushup(x);
}
int query(int x,int l,int r,int ql,int qr)
{
    if(val[x]>ql)return -1;
    if(l==r)return l;
    int mid=l+r>>1;
    if(qr>mid)
    {
        int res=query(x<<1|1,mid+1,r,ql,qr);
        if(res!=-1)return res;
    }
    if(ql<=mid)return query(x<<1,l,mid,ql,qr);
    return -1;
}
int main()
{
    read(n,m);
    scanf("%s",t+1);
    tl=strlen(t+1);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        AC1.insert(i,s);
        sl[i]=strlen(s);
        reverse(s,s+sl[i]);
        AC2.insert(i,s);
        rev[i]=s;
    }
    AC1.build(),AC2.build();
    for(int i=1,u=0;i<=tl;i++)
    {
        u=AC1.tr[u][t[i]-'a'];
        sum[i]=sum[i-1]+AC1.ed[u];
        g[i]=AC1.p[u];
    }
    for(int i=1;i<=n;i++)
    {
        f[i].resize(sl[i]);
        for(int j=0,u=0;j<sl[i];j++)
        {
            u=AC2.tr[u][rev[i][j]-'a'];
            f[i][j]=AC2.ed[u];
            if(j)f[i][j]+=f[i][j-1];
        }
    }
    build(1,1,tl);
    while(m--)
    {
        int l,r;
        read(l,r);
        int p=query(1,1,tl,l,r);
        if(p==-1)printf("%lld ",sum[r]-sum[l-1]);
        else printf("%lld ",sum[r]-sum[p]+f[g[p]][p-l]);
    }
    return 0;
}