Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_DEPRECATE
- #include <stdio.h>
- #include <iostream>
- #include <algorithm>
- #include <math.h>
- #include <memory>
- #include <memory.h>
- #include <set>
- #include <vector>
- #include <time.h>
- #include <string>
- #include <string.h>
- #include <queue>
- #include <stdlib.h>
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef vector <int> vi;
- typedef pair < int, int > pi;
- #define pb push_back
- #define mp make_pair
- void solve ();
- int main()
- {
- #ifdef _DEBUG
- freopen ("in.txt", "r", stdin);
- //freopen ("out.txt", "w", stdout);
- #endif
- int t;
- scanf ("%d", &t);
- getchar();
- while (t--)
- solve();
- }
- //#define int li
- const int maxlen=100500;
- char s[maxlen];
- int p[maxlen];
- int n;
- int c[maxlen];
- int cnt[maxlen];
- int pn[maxlen], cn[maxlen];
- int lcp[maxlen], lcpn[maxlen], lpos[maxlen], rpos[maxlen];
- int classes=1;
- const int shift=1<<16;
- int tree[2*shift+2];
- void rmq_build ()
- {
- memset (tree, 0, sizeof (tree));
- for ( int i=shift; i<shift+n; i++ )
- tree[i]=lcp[i-shift];
- for (int i=shift-1; i>0; i-- )
- tree[i]=min ( tree[2*i], tree[2*i+1] );
- }
- int rmq ( int l, int r )
- {
- if (l>r)
- return 1<<30;
- if ( (l%2) )
- return min ( tree[l], rmq(l+1, r) );
- if ( !(r%2) )
- return min ( tree[r], rmq (l, r-1) );
- return rmq (l/2, r/2);
- }
- void solve ()
- {
- gets (s);
- n=strlen(s)+1;
- memset (lcp, 0, sizeof (lcp));
- memset (cnt, 0, sizeof (cnt));
- for ( int i=0; i<n; i++ )
- cnt[s[i]]++;
- for (int i=1; i<=256; i++)
- cnt[i]+=cnt[i-1];
- for ( int i=0; i<n; i++ )
- p[--cnt[s[i]]]=i;
- c[p[0]]=0;
- for ( int i=1; i<n; i++ )
- {
- if ( s[p[i]]!=s[p[i-1]] )
- classes++;
- else
- lcp[i-1]=1;
- c[p[i]]=classes-1;
- }
- for ( int h=0; (1<<h)<n; h++ )
- {
- for (int i=0; i<n; ++i)
- rpos[c[p[i]]] = i;
- for (int i=n-1; i>=0; --i)
- lpos[c[p[i]]] = i;
- for ( int i=0; i<n; i++ )
- {
- pn[i]=p[i]-(1<<h);
- if (pn[i]<0)
- pn[i]+=n;
- }
- memset (cnt, 0, sizeof (cnt));
- for (int i=0; i<n; i++)
- cnt[c[pn[i]]]++;
- for (int i=1; i<classes; i++)
- cnt[i]+=cnt[i-1];
- for (int i=n-1; i>=0; i--)
- p[--cnt[c[pn[i]]]]=pn[i];
- cn[p[0]]=0;
- classes=1;
- for (int i=1; i<n; i++)
- {
- int m1=(p[i]+(1<<h))%n, m2=(p[i-1]+(1<<h))%n;
- if ( c[p[i]]!=c[p[i-1]] || c[m1]!=c[m2] )
- classes++;
- cn[p[i]]=classes-1;
- }
- rmq_build ();
- for (int i=0; i<n-1; ++i) {
- int a = p[i], b = p[i+1];
- if (c[a] != c[b])
- lcpn[i] = lcp[rpos[c[a]]];
- else {
- int aa = (a + (1<<h)) % n, bb = (b + (1<<h)) % n;
- lcpn[i] = (1<<h) + rmq (lpos[c[aa]]+shift, rpos[c[bb]]-1+shift);
- lcpn[i] = min (n, lcpn[i]);
- }
- }
- memcpy (lcp, lcpn, n * sizeof(int));
- memcpy (c, cn, n * sizeof(int));
- }
- li ans=0;
- for (int i=0; i<n-1; i++)
- {
- int len2=n-1-p[i+1]-lcp[i];
- ans+=(li)len2;
- }
- printf ("%lld\n", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement