daily pastebin goal
47%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2011 128 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <math.h>
  6. #include <memory>
  7. #include <memory.h>
  8. #include <set>
  9. #include <vector>
  10. #include <time.h>
  11. #include <string>
  12. #include <string.h>
  13. #include <queue>
  14. #include <stdlib.h>
  15. using namespace std;
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef vector <int> vi;
  19. typedef pair < int, int > pi;
  20. #define pb push_back
  21. #define mp make_pair
  22. void solve ();
  23. int main()
  24. {
  25. #ifdef _DEBUG
  26.         freopen ("in.txt", "r", stdin);
  27.         //freopen ("out.txt", "w", stdout);
  28. #endif
  29.         int t;
  30.         scanf ("%d", &t);
  31.         getchar();
  32.         while (t--)
  33.         solve();
  34. }
  35. //#define int li
  36. const int maxlen=100500;
  37. char s[maxlen];
  38. int p[maxlen];
  39. int n;
  40. int c[maxlen];
  41. int cnt[maxlen];
  42. int pn[maxlen], cn[maxlen];
  43. int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
  44. int classes=1;
  45. const int shift=1<<16;
  46. int tree[2*shift+2];
  47. void rmq_build ()
  48. {
  49.         memset (tree, 0, sizeof (tree));
  50.         for ( int i=shift; i<shift+n; i++ )
  51.                 tree[i]=lcp[i-shift];
  52.         for (int i=shift-1; i>0; i-- )
  53.                 tree[i]=min ( tree[2*i], tree[2*i+1] );
  54. }
  55. int rmq ( int l, int r )
  56. {
  57.         if (l>r)
  58.                 return 1<<30;
  59.         if ( (l%2) )
  60.                 return min ( tree[l], rmq(l+1, r) );
  61.         if ( !(r%2) )
  62.                 return min ( tree[r], rmq (l, r-1) );
  63.         return rmq (l/2, r/2);
  64. }
  65. void solve ()
  66. {
  67.         gets (s);
  68.         n=strlen(s)+1;
  69.         memset (lcp, 0, sizeof (lcp));
  70.         memset (cnt, 0, sizeof (cnt));
  71.         for ( int i=0; i<n; i++ )
  72.                 cnt[s[i]]++;
  73.         for (int i=1; i<=256; i++)
  74.                 cnt[i]+=cnt[i-1];
  75.         for ( int i=0; i<n; i++ )
  76.                 p[--cnt[s[i]]]=i;
  77.         c[p[0]]=0;
  78.         for ( int i=1; i<n; i++ )
  79.         {
  80.                 if ( s[p[i]]!=s[p[i-1]] )
  81.                         classes++;
  82.                 else
  83.                         lcp[i-1]=1;
  84.                 c[p[i]]=classes-1;
  85.         }
  86.         for ( int h=0; (1<<h)<n; h++ )
  87.         {
  88.                 for (int i=0; i<n; ++i)
  89.                 rpos[c[p[i]]] = i;
  90.                 for (int i=n-1; i>=0; --i)
  91.                 lpos[c[p[i]]] = i;
  92.  
  93.                 for ( int i=0; i<n; i++ )
  94.                 {
  95.                         pn[i]=p[i]-(1<<h);
  96.                         if (pn[i]<0)
  97.                                 pn[i]+=n;
  98.                 }
  99.                 memset (cnt, 0, sizeof (cnt));
  100.                 for (int i=0; i<n; i++)
  101.                         cnt[c[pn[i]]]++;
  102.                 for (int i=1; i<classes; i++)
  103.                         cnt[i]+=cnt[i-1];
  104.                 for (int i=n-1; i>=0; i--)
  105.                         p[--cnt[c[pn[i]]]]=pn[i];
  106.                 cn[p[0]]=0;
  107.                 classes=1;
  108.                 for (int i=1; i<n; i++)
  109.                 {
  110.                         int m1=(p[i]+(1<<h))%n, m2=(p[i-1]+(1<<h))%n;
  111.                         if ( c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2] )
  112.                                 classes++;
  113.                         cn[p[i]]=classes-1;
  114.                 }
  115.  
  116.                 rmq_build ();
  117.                 for (int i=0; i<n-1; ++i) {
  118.                 int a = p[i],  b = p[i+1];
  119.                 if (c[a] != c[b])
  120.                         lcpn[i] = lcp[rpos[c[a]]];
  121.                 else {
  122.                         int aa = (a + (1<<h)) % n,  bb = (b + (1<<h)) % n;
  123.                         lcpn[i] = (1<<h) + rmq (lpos[c[aa]]+shift, rpos[c[bb]]-1+shift);
  124.                         lcpn[i] = min (n, lcpn[i]);
  125.                 }
  126.         }
  127.         memcpy (lcp, lcpn, n * sizeof(int));
  128.         memcpy (c, cn, n * sizeof(int));
  129.         }
  130.         li ans=0;
  131.         for (int i=0; i<n-1; i++)
  132.         {
  133.                 int len2=n-1-p[i+1]-lcp[i];
  134.                 ans+=(li)len2;
  135.         }
  136.         printf ("%lld\n", ans);
  137. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top