fork download
copy 
  1. // ~~ icebear love attttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebearat"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 2e5 + 5;
  38. int lenStr, numStr, ans[N], cntSame[N];
  39. string pattern;
  40. string str[N];
  41. vector<int> startPos[N], endPos[N];
  42. map<string, int> id;
  43. int cntStart[N];
  44. bool haveStart[N];
  45.  
  46. struct Aho_Corasick {
  47.     const static int MAX_NODE = 26;
  48.     const static char LOWER = 'a';
  49.     struct Node {
  50.         Node *link, *child[MAX_NODE], *go[MAX_NODE], *nearAsk;
  51.         int id;
  52.         vector<Node*> G;
  53.         Node() {
  54.             link = nearAsk = NULL;
  55.             REP(i, MAX_NODE) child[i] = go[i] = NULL;
  56.             id = 0;
  57.         }
  58.     };
  59.  
  60.     Node *root;
  61.     Aho_Corasick() {
  62.         root = new Node();
  63.     }
  64.  
  65.     void add(string &s, int id) {
  66.         Node *p = root;
  67.         for(char c : s) {
  68.             int pos = c - LOWER;
  69.             if (p -> child[pos] == NULL) {
  70.                 p -> child[pos] = new Node();
  71.                 p -> go[pos] = p -> child[pos];
  72.             }
  73.             p = p -> child[pos];
  74.         }
  75.         p -> id = id;
  76.     }
  77.  
  78.     void BFS() {
  79.         queue<Node*> q;
  80.         REP(pos, MAX_NODE) {
  81.             if (root -> child[pos] == NULL) {
  82.                 root -> child[pos] = new Node();
  83.                 root -> go[pos] = root -> child[pos];
  84.             }
  85.             q.push(root -> child[pos]);
  86.             root -> G.pb(root -> child[pos]);
  87.             root -> child[pos] -> link = root; 
  88.         }
  89.  
  90.         while(!q.empty()) {
  91.             auto p = q.front(); q.pop();
  92.             REP(pos, MAX_NODE) {
  93.                 if (p -> child[pos] == NULL) {
  94.                     p -> go[pos] = p -> link -> go[pos];   
  95.                 } else {
  96.                     q.push(p -> child[pos]);
  97.                     p -> child[pos] -> link = p -> link -> go[pos];
  98.                     p -> link -> go[pos] -> G.pb(p -> child[pos]);
  99.                 }
  100.             }
  101.         }
  102.     }
  103.  
  104.     void DFS(Node *u, Node *preAsk) {
  105.         u -> nearAsk = preAsk;
  106.         for(auto v : u -> G) {
  107.             if (u -> id == 0) DFS(v, preAsk);
  108.             else DFS(v, u);
  109.         }
  110.     }
  111.  
  112.     void queryPattern(string &s) {
  113.         Node *p = root;
  114.         REP(i, (int)s.size()) {
  115.             int pos = s[i] - LOWER;
  116.             p = p -> go[pos];
  117.             auto tmp = p;
  118.  
  119.             if (tmp -> id == 0) tmp = tmp -> nearAsk;
  120.             while(tmp != NULL) {
  121.                 endPos[tmp -> id].pb(i);
  122.                 tmp = tmp -> nearAsk;
  123.             }
  124.         }
  125.     }
  126. } aho;
  127.  
  128. ll countGlobal(int i) {
  129.     ll ans = 0;
  130.     for(int pos : startPos[i]) cntStart[pos] -= cntSame[i];
  131.     for(int pos : endPos[i]) ans += 1LL * cntSame[i] * cntStart[pos + 1];
  132.     for(int pos : startPos[i]) cntStart[pos] += cntSame[i];
  133.     return ans;
  134. }
  135.  
  136. ll countInternal(int i) {
  137.     ll ans = 0;
  138.     for(int pos : startPos[i]) haveStart[pos] = true;
  139.     for(int pos : endPos[i]) if (haveStart[pos + 1]) 
  140.         ans += 1LL * cntSame[i] * cntSame[i];
  141.     for(int pos : startPos[i]) haveStart[pos] = false;
  142.     return ans;
  143. }
  144.  
  145. void init(void) {
  146.     cin >> pattern;
  147.     lenStr = (int)pattern.size();
  148.     cin >> numStr;
  149.     FOR(i, 1, numStr) {
  150.         cin >> str[i];
  151.         if (id[str[i]] == 0) id[str[i]] = i;
  152.         cntSame[id[str[i]]]++;
  153.     }
  154. }
  155.  
  156. void process(void) {
  157.     FOR(i, 1, numStr) if (id[str[i]] == i) {
  158.         aho.add(str[i], i);
  159.     }
  160.     aho.BFS();
  161.     aho.DFS(aho.root, NULL);
  162.     aho.queryPattern(pattern);
  163.     FOR(i, 1, numStr) if (id[str[i]] == i) {
  164.         for(int pos : endPos[i]) {
  165.             int start_pos = pos - (int)str[i].size() + 1;
  166.             startPos[i].pb(start_pos);
  167.             cntStart[start_pos] += cntSame[i];
  168.         }
  169.     }
  170.  
  171.     ll ans = 0;
  172.     FOR(i, 1, numStr) if (id[str[i]] == i) {
  173.         ans += countGlobal(i);
  174.         ans += countInternal(i);
  175.     }
  176.     cout << ans << '\n';
  177. }
  178.  
  179. int main() {
  180.     ios_base::sync_with_stdio(0);
  181.     cin.tie(0); cout.tie(0);
  182.     if (fopen(task".inp", "r")) {
  183.         freopen(task".inp", "r", stdin);
  184.         freopen(task".out", "w", stdout);
  185.     }
  186.     int tc = 1;
  187. //    cin >> tc;
  188.     while(tc--) {
  189.         init();
  190.         process();
  191.     }
  192.     return 0;
  193. }
  194.  
  195.  
Success #stdin #stdout 0.01s 19236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/rxYwpv
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!