題目鏈接

題意

1個匹配串$T$，$n$個模式串$S$，求$\sum _{i=1}^n\sum _{j=1}^{n}F(T,S_i+S_j)$，$F(S,T)$表示T在S中出現(xiàn)的次數(shù)。

思路

$F$函數(shù)可以用$AC$自動機來找，但是枚舉所有的$<i,j>$復雜度過高，可以建兩個$AC$自動機，一個正向一個反向。$dfs$預處理每個節(jié)點的匹配情況，枚舉兩個串的結合點。

#include <bits/stdc++.h> const int maxn = 2e5 + 5; using namespace std; struct Trie{int nex[maxn][26], fail[maxn], end[maxn];int root, p;inline int newnode() {for (int i = 0; i < 26; ++i) {nex[p][i] = -1;}end[p++] = 0;return p - 1;}inline void init() {p = 0;root = newnode();}inline void insert(char *buf) {int now = root;for (int i = 0; buf[i]; ++i) {if (nex[now][buf[i]-'a'] == -1) nex[now][buf[i]-'a'] = newnode();now = nex[now][buf[i]-'a'];}end[now]++;} inline void build() {queue<int> que;fail[root] = root;for (int i = 0; i < 26; ++i) {if (nex[root][i] == -1)nex[root][i] = root;else {fail[nex[root][i]] = root;que.push(nex[root][i]);}}while (!que.empty()) {int now = que.front();que.pop();for (int i = 0; i < 26; ++i) {if (nex[now][i] == -1) nex[now][i] = nex[fail[now]][i];else {fail[nex[now][i]] = nex[fail[now]][i];que.push(nex[now][i]);}}}}long long num[maxn], dp[maxn]; // num記錄節(jié)點i匹配的個數(shù), dp輔助得到所有適配數(shù)量long long dfs(int now) {if (now == root) return 0;if (dp[now] != -1) return dp[now];return dp[now] = end[now] + dfs(fail[now]);}inline void solve(char *buf) { fill(num, num+maxn, 0);fill(dp, dp+maxn, -1);int now = root;for (int i = 0; buf[i]; ++i) {now = nex[now][buf[i]-'a'];num[i] = dfs(now);} }inline long long query(char *buf) {int now = root;long long cnt = 0;for (int i = 0; buf[i]; ++i) {now = nex[now][buf[i]-'a'];int tmp = now;while (tmp != root && end[tmp] != -1) {cnt += end[tmp];end[tmp] = -1; // 統(tǒng)計種類，加速tmp = fail[tmp];}}return cnt;} }L, R;char s[maxn], t[maxn]; int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);scanf("%s", s);int lens = strlen(s);int n;scanf("%d", &n);L.init();R.init();while (n--) {scanf("%s", t);L.insert(t);int lent = strlen(t);reverse(t, t+lent);R.insert(t);}L.build(); R.build();L.solve(s);reverse(s, s+lens); R.solve(s);long long ans = 0;for (int i = 0; i < lens-1; ++i) {ans += L.num[i] * R.num[lens-2-i];}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的CF1202 - E. You Are Given Some Strings...(AC自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。