[CF1202E You Are Given Some Strings...] Solution

Publish Date: 2023-01-08

Update Date: 2023-05-18

[CF1202E You Are Given Some Strings…] Solution

Problem Link: CF1202E You Are Given Some Strings…

Problem Statement:

Given a text string $t$ and $n$ pattern strings $s_i$, find
$\sum_{i=1}^n\sum_{j=1}^nf(s_i + s_j)$
$f(s)$ is defined as the number of occurrences of $s$ in $t$, and $s_i + s_j$ is defined as the splice strings $s_i$ and $s_j$.

Input:

One line $t$, one line $n$, and the next $n$ line $s_i$.

Output:

Answer.

Data Range:

$1\le |t|,\sum |s_i| \le 2\times 10^5$ .

This kind of question must consider the contribution of a certain string.

Here we consider the enumeration division point $x$. Denote the point before as $s_i$ and the point after as $s_j$

Count the number of $f(x),g(x+1)$ before and after each $x$.

How do we count them? Notice that $f(x)$ is actually how many known substrings are in the suffix of $t_{1 \cdots x}$ and $g(x)$ is the reverse of $f(x)$ .

This is something that can be messed with using AC automata. That is, build the AC automaton directly on the pattern string and run $t$ through it.

Consider that the fail pointer points to the longest suffix from the root to the current string, and then the request is equivalent to the number of suffixes for the pattern string.

As we know from the AC automaton’s code, this is simply a matter of summing over the fail tree.

Time Complexity is $\mathcal{O}(\sum |s_i| \times |\Sigma|)$

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5+15))

struct Trie
{
    queue<int> q;
    int tot,trie[N][26],ed[N],fail[N];
    void insert(char *s)
    {
        int u = 0;
        for(int i=1; s[i]; i++)
        {
            int c = s[i] - 'a';
            if(!trie[u][c]) trie[u][c] = ++tot;
            u = trie[u][c];
        }
        ++ed[u];
    }
    void build()
    {
        for(int i=0; i<26; i++) if(trie[0][i]) q.push(trie[0][i]);
        for(int u; !q.empty(); )
        {
            u = q.front(); q.pop();
            for(int i=0; i<26; i++)
            {
                if(trie[u][i])
                {
                    fail[trie[u][i]] = trie[fail[u]][i];
                    ed[trie[u][i]] += ed[fail[trie[u][i]]]; q.push(trie[u][i]);
                }else trie[u][i] = trie[fail[u]][i];
            }
        }
    }
    void query(char *s,int *f)
    {
        int u = 0;
        for(int i=1; s[i]; i++)
        { u = trie[u][s[i] - 'a']; f[i] = ed[u]; }
    }
}tr1,tr2;
char s[N],t[N]; int f[N],g[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,l; cin >> (t + 1) >> n; l = strlen(t + 1);
    for(int i=1; i<=n; i++)
    {
        cin >> (s + 1); tr1.insert(s);
        reverse(s + 1, s + 1 + strlen(s + 1)); tr2.insert(s);
    }
    tr1.build(); tr2.build(); tr1.query(t,f);
    reverse(t + 1, t + 1 + l); tr2.query(t,g);
    // for(int i=1; i<=l; i++) cout << f1[i] << " \n"[i==l];
    // for(int i=1; i<=l; i++) cout << f2[i] << " \n"[i==l];
    int res = 0;
    for(int i=1; i<=l; i++) res += f[i] * g[l - i];
    cout << res << '\n';
    return 0;
}