peltorator

Dynamic Aho

Aug 11th, 2018
155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const int LG = 20; // change
  2.  
  3. struct aho
  4. {
  5.     vector<vector<int> > g, gr;
  6.     vector<string> str;
  7.     int root;
  8.     int sz;
  9.     vector<ll> ending;
  10.     vector<int> link;
  11.     char firstlet;
  12.     int numlet = 0;
  13.  
  14.     aho():
  15.         g(),
  16.         gr(),
  17.         str(),
  18.         root(0),
  19.         sz(0),
  20.         ending(),
  21.         link() {}
  22.  
  23.     aho(vector<string> q, char firlet = 'a') // change
  24.     {
  25.         firstlet = firlet;
  26.         sz = q.size();
  27.         str = q;
  28.         g.clear();
  29.         gr.clear();
  30.         ending.clear();
  31.         link.clear();
  32.         root = 0;
  33.         ending.assign(1, 0);
  34.         numlet = 0;
  35.         for (int i = 0; i < q.size(); i++)
  36.             for (int j = 0; j < q[i].size(); j++)
  37.                 numlet = max(numlet, q[i][j] - firstlet);
  38.         numlet++;
  39.         g.push_back(vector<int>(numlet, -1));
  40.         for (int i = 0; i < q.size(); i++)
  41.         {
  42.             int v = root;
  43.             for (int j = 0; j < q[i].size(); j++)
  44.             {
  45.                 if (g[v][q[i][j] - firstlet] == -1)
  46.                 {
  47.                     g[v][q[i][j] - firstlet] = g.size();
  48.                     g.push_back(vector<int>(numlet, -1));
  49.                     ending.push_back(0);
  50.                 }
  51.                 v = g[v][q[i][j] - firstlet];
  52.             }
  53.             ending[v]++;
  54.         }
  55.         link.assign(g.size(), -1);
  56.         link[root] = root;
  57.         queue<int> que;
  58.         que.push(root);
  59.         while (que.size())
  60.         {
  61.             int v = que.front();
  62.             que.pop();
  63.             for (int i = 0; i < numlet; i++)
  64.                 if (g[v][i] == -1)
  65.                 {
  66.                     if (v == root)
  67.                         g[v][i] = v;
  68.                     else
  69.                         g[v][i] = g[link[v]][i];
  70.                 }
  71.                 else
  72.                 {
  73.                     que.push(g[v][i]);
  74.                     if (v == root)
  75.                         link[g[v][i]] = v;
  76.                     else
  77.                         link[g[v][i]] = g[link[v]][i];
  78.                 }
  79.         }
  80.         gr.resize(g.size());
  81.         for (int i = 0; i < g.size(); i++)
  82.             if (i != root)
  83.                 gr[link[i]].push_back(i);
  84.         dfslink(root);
  85.     }
  86.  
  87.     void dfslink(int v)
  88.     {
  89.         for (int u : gr[v])
  90.         {
  91.             ending[u] += ending[v];
  92.             dfslink(u);
  93.         }
  94.     }
  95.  
  96.     ll find(string s) // change
  97.     {
  98.         ll ans = 0;
  99.         int v = root;
  100.         for (int i = 0; i < s.size(); i++)
  101.         {
  102.             v = g[v][s[i] - firstlet];
  103.             ans += ending[v];
  104.         }
  105.         return ans;
  106.     }
  107. };
  108.  
  109. struct DynamicAho
  110. {
  111.     aho a[LG];
  112.     aho b[LG];
  113.     int asz, bsz;
  114.     char firstlet;
  115.     DynamicAho(char firlet = 'a') // change
  116.     {
  117.         firstlet = firlet;
  118.         asz = bsz = 0;
  119.         for (int i = 0; i < LG; i++)
  120.             a[i] = b[i] = aho(vector<string>(0), firstlet);
  121.     }
  122.  
  123.     void addString(string s)
  124.     {
  125.         int i = 0;
  126.         vector<string> newaho;
  127.         newaho.push_back(s);
  128.         while (a[i].sz > 0)
  129.         {
  130.             for (int j = 0; j < a[i].str.size(); j++)
  131.                 newaho.push_back(a[i].str[j]);
  132.             a[i++] = aho();
  133.         }
  134.         a[i] = aho(newaho);
  135.     }
  136.  
  137.     void deleteString(string s)
  138.     {
  139.         int i = 0;
  140.         vector<string> newaho;
  141.         newaho.push_back(s);
  142.         while (b[i].sz > 0)
  143.         {
  144.             for (int j = 0; j < b[i].str.size(); j++)
  145.                 newaho.push_back(b[i].str[j]);
  146.             b[i++] = aho();
  147.         }
  148.         b[i] = aho(newaho);
  149.  
  150.     }
  151.  
  152.     ll find(string s) // change
  153.     {
  154.         ll ans = 0;
  155.         for (int j = 0; j < LG; j++)
  156.         {
  157.             if (a[j].sz > 0)
  158.                 ans += a[j].find(s);
  159.             if (b[j].sz > 0)
  160.                 ans -= b[j].find(s);
  161.         }
  162.         return ans;
  163.     }
  164. };
RAW Paste Data