Codeforces 1202E You Are Given Some Strings…

正文索引 [隐藏]

题目大意
题解
代码

题目大意

给你一个字符串 $T$ 和 $n$ 个字符串 $S_1, S_2, \cdot, S_n$，定义 $A+B=AB$ 为字符串拼接操作，$f(A)$ 为字符串 $A$ 在 $T$ 中出现的次数，求 $\sum_{i=1}^n\sum_{j=1}^n f(S_i + S_j)$。

数据范围：$1\leq n, |T|, \sum_{i=1}^n |S_i| \leq 2\times 10^5$

题解

先生成所有拼接字符串再匹配很困难，因为拼接字符串是的数量是平方级别的。

我们可以考虑分别匹配拼接字符串的左部和右部，然后通过计数的方式统计答案。
我们枚举拼接点 $i$，那么这个拼接点对于答案的贡献就是 $pq$。其中，在 $T$ 中出现的所有字符串 $S$ 刚好在以 $T_i$ 字符结束的数量为 $p$，刚好以 $T_{i+1}$ 打头的数量为 $q$。

感受一下就是，假设 $T=abcdef, {S} = {c, bc, d, de, def}$，我们枚举了一个拼接点 $i=2$，即 $abc|def$。
$$
\begin{aligned}
T = abc &| def\
Left = c&|\
bc&|\
Right = &| d\
&| de\
&| def\
\end{aligned}
$$
那么很明显这个是乘法原理，这个拼接点对答案的贡献为 $2\times 3 = 6$。

所以现在我们只需要计算字符串集合 ${S}$ 在 $T$ 中匹配以每个位置结尾的匹配成功数量是多少以及以每个位置开头匹配成功的数量是多少就行了。
再想一下，这两个问题其实是镜像的，我们只需要将 ${S}$ 里的字符串与 $T$ 全部反转，那么这两个问题就等价了。
这样的匹配问题可以使用 AC自动机解决。

最后再使用乘法原理统计一下答案就行了。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

class AhoCorasiek{
protected:
    const static int N=2e5+50;
    const static int M=26;
    queue<int> que;

    int create(){
        int x=++numn;
        memset(node[x].ch, -1, sizeof(node[x].ch));
        node[x].cnt=node[x].fail=0;
        return x;
    }

public:
    struct Node{
        int ch[M];
        int cnt, fail;
    }node[N];
    int numn, rt;

    void init(){ numn=0, rt=create(); }

    void insert(char str[], int l){
        int x=rt;
        for (int i=0; i<l; ++i){
            int c=str[i]-'a';
            if (node[x].ch[c]==-1) node[x].ch[c]=create();
            x=node[x].ch[c];
        }
        ++node[x].cnt;
    }

    int next(int x, int c){
        while(x!=rt && node[x].ch[c]==-1) x=node[x].fail;
        if (node[x].ch[c]==-1) return rt;
        return node[x].ch[c];
    }

    void build(){
        while(!que.empty()) que.pop();

        node[rt].fail=rt;
        for (int c=0, v; c<M; ++c){
            v=node[rt].ch[c];
            if (v!=-1) que.push(v), node[v].fail=rt;
        }

        while(!que.empty()){
            int x=que.front(); que.pop();
            node[x].cnt+=node[node[x].fail].cnt;
            for (int c=0, v; c<M; ++c){
                v=node[x].ch[c];
                if (v!=-1) que.push(v), node[v].fail=next(node[x].fail, c);
            }
        }
    }
}str, rev;


const int MAXN=2e5+50;
char T[MAXN], S[MAXN];
int pre[MAXN], suf[MAXN];
int main(){
    // freopen("in.txt", "r", stdin);

    str.init(); rev.init();
    int n, m; scanf("%s%d", T, &n); m=strlen(T);
    for (int i=0, l; i<n; i++){
        scanf("%s", S); l=strlen(S);
        str.insert(S, l); 
        reverse(S, S+l);
        rev.insert(S, l);
    }

    str.build(); rev.build();

    for (int i=0, x=str.rt; i<m; ++i){
        x=str.next(x, T[i]-'a');
        pre[i]=str.node[x].cnt;
    }
    for (int i=m-1, x=rev.rt; i>=0; --i){
        x=rev.next(x, T[i]-'a');
        suf[i]=rev.node[x].cnt;
    }

    long long ans=0;
    for (int i=1; i<m; ++i) ans+=1LL*pre[i-1]*suf[i];

    printf("%lld\n", ans);
    return 0;
}

100

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

class AhoCorasiek{

protected:

const static int N=2e5+50;

const static int M=26;

queue<int> que;

int create(){

int x=++numn;

memset(node[x].ch, -1, sizeof(node[x].ch));

node[x].cnt=node[x].fail=0;

return x;

}

public:

struct Node{

int ch[M];

int cnt, fail;

}node[N];

int numn, rt;

void init(){ numn=0, rt=create(); }

void insert(char str[], int l){

int x=rt;

for (int i=0; i<l; ++i){

int c=str[i]-'a';

if (node[x].ch[c]==-1) node[x].ch[c]=create();

x=node[x].ch[c];

}

++node[x].cnt;

}

int next(int x, int c){

while(x!=rt && node[x].ch[c]==-1) x=node[x].fail;

if (node[x].ch[c]==-1) return rt;

return node[x].ch[c];

}

void build(){

while(!que.empty()) que.pop();

node[rt].fail=rt;

for (int c=0, v; c<M; ++c){

v=node[rt].ch[c];

if (v!=-1) que.push(v), node[v].fail=rt;

}

while(!que.empty()){

int x=que.front(); que.pop();

node[x].cnt+=node[node[x].fail].cnt;

for (int c=0, v; c<M; ++c){

v=node[x].ch[c];

if (v!=-1) que.push(v), node[v].fail=next(node[x].fail, c);

}

}str, rev;

const int MAXN=2e5+50;

char T[MAXN], S[MAXN];

int pre[MAXN], suf[MAXN];

int main(){

// freopen("in.txt", "r", stdin);

str.init(); rev.init();

int n, m; scanf("%s%d", T, &n); m=strlen(T);

for (int i=0, l; i<n; i++){

scanf("%s", S); l=strlen(S);

str.insert(S, l);

reverse(S, S+l);

rev.insert(S, l);

}

str.build(); rev.build();

for (int i=0, x=str.rt; i<m; ++i){

x=str.next(x, T[i]-'a');

pre[i]=str.node[x].cnt;

}

for (int i=m-1, x=rev.rt; i>=0; --i){

x=rev.next(x, T[i]-'a');

suf[i]=rev.node[x].cnt;

}

long long ans=0;

for (int i=1; i<m; ++i) ans+=1LL*pre[i-1]*suf[i];

printf("%lld\n", ans);

return 0;

}

一	二	三	四	五	六	日
						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

WNJXYKの博客

喂你脚下有坑