Sunday, December 15, 2019

[LOJ] 1428 - Melody Comparison

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1428 - Melody Comparison
Source            : Light OJ
Category          : String, Data Structure
Algorithm         : Suffix Tree, KMP, Sparse Table
Verdict           : Accepted

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. static const int maxn = 1e5 + 5;  
  6. static const int inf  = 1e9 + 5;  
  7. static const int logn = 19;  
  8.   
  9. struct Node  
  10. {  
  11.       int l;  
  12.       int r;  
  13.       int par;  
  14.       int link;  
  15.       map <char,int> next;  
  16.       Node(int l = 0, int r = 0, int par = -1)  
  17.             : l(l)  
  18.             , r(r)  
  19.             , par(par)  
  20.             , link(-1) {}  
  21.   
  22.       void clean()  
  23.       {  
  24.             l = 0;  
  25.             r = 0;  
  26.             par = -1;  
  27.             link = -1;  
  28.             next.clear();  
  29.       }  
  30.       int len()  
  31.       {  
  32.             return r - l;  
  33.       }  
  34.       int &get(char c)  
  35.       {  
  36.             if (!next.count(c)) next[c] = -1;  
  37.             return next[c];  
  38.       }  
  39. };  
  40.   
  41. Node t[maxn];  
  42. string s;  
  43. int sz;  
  44. int n;  
  45.   
  46. struct state  
  47. {  
  48.       int v, pos;  
  49.       state() {}  
  50.       state(int v, int pos) : v(v), pos(pos) {}  
  51. };  
  52.   
  53. state ptr;  
  54.   
  55. state go(state st, int l, int r)  
  56. {  
  57.       while (l < r)  
  58.       {  
  59.             if (st.pos == t[st.v].len())  
  60.             {  
  61.                   st = state(t[st.v].get(s[l]), 0);  
  62.                   if (st.v == -1) return st;  
  63.             }  
  64.             else  
  65.             {  
  66.                   assert(t[st.v].l + st.pos >= 0);  
  67.                   if (s[ t[st.v].l + st.pos ] != s[l])  
  68.                         return state(-1, -1);  
  69.                   if (r - l < t[st.v].len() - st.pos)  
  70.                         return state(st.v, st.pos + r - l);  
  71.                   l += t[st.v].len() - st.pos;  
  72.                   st.pos = t[st.v].len();  
  73.             }  
  74.       }  
  75.       return st;  
  76. }  
  77.   
  78. int split(state st)  
  79. {  
  80.       if (st.pos == t[st.v].len())  
  81.             return st.v;  
  82.       if (st.pos == 0)  
  83.             return t[st.v].par;  
  84.       Node v = t[st.v];  
  85.       int id = sz++;  
  86.       t[id] = Node(v.l, v.l + st.pos, v.par);  
  87.       t[v.par].get(s[v.l]) = id;  
  88.       t[id].get(s[v.l + st.pos]) = st.v;  
  89.       assert(st.v >= 0);  
  90.       t[st.v].par = id;  
  91.       t[st.v].l += st.pos;  
  92.       return id;  
  93. }  
  94.   
  95. int get_link(int v)  
  96. {  
  97.       if (t[v].link != -1)  
  98.             return t[v].link;  
  99.       if (t[v].par == -1)  
  100.             return 0;  
  101.       int to = get_link(t[v].par);  
  102.       return t[v].link = split(go(state(to, t[to].len()), t[v].l + (t[v].par == 0), t[v].r));  
  103. }  
  104.   
  105. void tree_extend(int pos)  
  106. {  
  107.       for(;;)  
  108.       {  
  109.             state nptr = go(ptr, pos, pos + 1);  
  110.             if (nptr.v != -1)  
  111.             {  
  112.                   ptr = nptr;  
  113.                   return;  
  114.             }  
  115.             int mid = split(ptr);  
  116.             int leaf = sz++;  
  117.             t[leaf] = Node(pos, n, mid);  
  118.             t[mid].get(s[pos]) = leaf;  
  119.             ptr.v = get_link(mid);  
  120.             ptr.pos = t[ptr.v].len();  
  121.             if (!mid) break;  
  122.       }  
  123. }  
  124.   
  125. void build_tree()  
  126. {  
  127.       sz = 1;  
  128.       ptr = {0, 0};  
  129.       for (int i = 0; i < maxn; i++) t[i].clean();  
  130.       for (int i = 0; i < n; i++) tree_extend(i);  
  131. }  
  132.   
  133. vector <int> longestPrefixSuffix(string &pat)  
  134. {  
  135.       vector <int> lps;  
  136.       lps.push_back(0);  
  137.       int len = pat.size();  
  138.       int i = 1;  
  139.       int j = 0;  
  140.       while (i < len)  
  141.       {  
  142.             if (pat[i] == pat[j])  
  143.             {  
  144.                   i++;  
  145.                   j++;  
  146.                   lps.push_back(j);  
  147.             }  
  148.             else  
  149.             {  
  150.                   if (j)  
  151.                   {  
  152.                         j = lps[j - 1];  
  153.                   }  
  154.                   else  
  155.                   {  
  156.                         i++;  
  157.                         lps.push_back(0);  
  158.                   }  
  159.             }  
  160.       }  
  161.       return lps;  
  162. }  
  163.   
  164. int occ[maxn];  
  165.   
  166. void kmp(string &text, string &pat)  
  167. {  
  168.       int lenText = text.size();  
  169.       for (int i = 0; i < lenText; i++) occ[i] = inf;  
  170.       int lenPat = pat.size();  
  171.       vector <int> lps = longestPrefixSuffix(pat);  
  172.       int i = 0;  
  173.       int j = 0;  
  174.       while (i < lenText)  
  175.       {  
  176.             if (text[i] == pat[j])  
  177.             {  
  178.                   i++;  
  179.                   j++;  
  180.             }  
  181.             if (j == lenPat)  
  182.             {  
  183.                   occ[i - 1] = i - 1;  
  184.                   j = lps[j - 1];  
  185.             }  
  186.             else if (i < lenText && text[i] != pat[j])  
  187.             {  
  188.                   if (j) j = lps[j - 1];  
  189.                   else i++;  
  190.             }  
  191.       }  
  192. }  
  193.   
  194. int Table[logn][maxn];  
  195.   
  196. void build_sparse_table()  
  197. {  
  198.       for (int i = 0; i < n; i++) Table[0][i] = occ[i];  
  199.       for (int k = 1; (1 << k) <= n; k++)  
  200.       {  
  201.             for (int i = 0; i + (1 << (k - 1)) < n; i++)  
  202.             {  
  203.                   int x = Table[k - 1][i];  
  204.                   int y = Table[k - 1][i + (1 << (k - 1))];  
  205.                   Table[k][i] = min(x, y);  
  206.             }  
  207.       }  
  208. }  
  209.   
  210. int query(int i, int j)  
  211. {  
  212.       int k = log2(j - i + 1);  
  213.       int x = Table[k][i];  
  214.       int y = Table[k][j + 1 - (1 << k)];  
  215.       return min(x, y);  
  216. }  
  217.   
  218. string pat;  
  219. int m;  
  220.   
  221. long long dfs(int u = 0, int sze = 0)  
  222. {  
  223.       long long sum = 0;  
  224.       for (auto it : t[u].next)  
  225.       {  
  226.             int v = it.second;  
  227.             int l = t[v].l;  
  228.             int r = t[v].r - 1;  
  229.             int need = max(0, m - sze);  
  230.             if (t[v].len() < need)  
  231.             {  
  232.                   sum += t[v].len() + dfs(v, sze + t[v].len());  
  233.             }  
  234.             else  
  235.             {  
  236.                   int newl = l;  
  237.                   int newr = r;  
  238.                   if (need) newl = l + need - 1;  
  239.                   int ind = query(newl, newr);  
  240.                   if (ind == inf)  
  241.                   {  
  242.                         sum += t[v].len() + dfs(v, sze + t[v].len());  
  243.                   }  
  244.                   else  
  245.                   {  
  246.                         int add = max(0, ind - l);  
  247.                         sum += add;  
  248.                   }  
  249.             }  
  250.       }  
  251.       return sum;  
  252. }  
  253.   
  254. signed main()  
  255. {  
  256.       ios_base::sync_with_stdio(false);  
  257.       cin.tie(nullptr);  
  258.       cout.tie(nullptr);  
  259.   
  260.       #ifndef ONLINE_JUDGE  
  261.             freopen("in.txt""r", stdin);  
  262.       #endif // ONLINE_JUDGE  
  263.   
  264.       int tc;  
  265.       cin >> tc;  
  266.       for (int tcase = 1; tcase <= tc; tcase++)  
  267.       {  
  268.             cin >> s >> pat;  
  269.             n = s.size();  
  270.             m = pat.size();  
  271.             build_tree();  
  272.             kmp(s, pat);  
  273.             build_sparse_table();  
  274.             cout << "Case " << tcase << ": " << dfs() << '\n';  
  275.       }  
  276. }  

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.