Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> ii;
- #define S second
- #define F first
- vector< vector< int > > Rank;
- map< ii , int > Cnt;
- vector< ii > Seg;
- string s;
- int n ,q;
- inline string Read()
- {
- const int N = 4e5+5;
- static char Buff[N];
- scanf("\n%s",Buff);
- return Buff;
- }
- void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n)
- {
- int N = max(300,n);
- vector< int > Cnt(N,0);
- vector< int > tempSA(n);
- for(int i = 0 ; i < n ; i++)
- Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;
- for(int i = 0, sum = 0 ; i < N ; i++)
- {
- int t = Cnt[i];
- Cnt[i] = sum;
- sum += t;
- }
- for(int i = 0 ; i < n ; i++)
- tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];
- SA = tempSA;
- }
- void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n)
- {
- CountSort(SA ,RA ,s ,n);
- CountSort(SA ,RA ,f ,n);
- }
- vector< vector< int > > ConstructSA(string &s ,int n)
- {
- vector< vector< int > > Rank((int)log2(n) ,vector< int >(n));
- vector< int > tempRA(n ,0) ,RA(n ,0) ,SA(n ,0);
- for(int i = 0 ; i < n ; i++) RA[i] = (int)s[i];
- for(int i = 0 ; i < n ; i++) SA[i] = i;
- for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 )
- {
- RadixSort(SA ,RA ,k ,0 ,n);
- int r = tempRA[ SA[0] ] = 0;
- for(int i = 1 ; i < n ; i++)
- {
- bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
- bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
- RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
- tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
- }
- Rank[ (int)log2(k) ] = RA = tempRA;
- }
- return Rank;
- }
- inline int Calc(ii a ,ii b){
- int LenA = a.S - a.F + 1;
- int LenB = b.S - b.F + 1;
- int Len = min(LenA ,LenB);
- int Log = log2( Len );
- ii A = ii( Rank[Log][a.F] , Rank[Log][ a.S - (1 << Log) + 1 ] );
- ii B = ii( Rank[Log][b.F] , Rank[Log][ b.S - (1 << Log) + 1 ] );
- if( A.F < B.F ) return +1;
- if( A.F > B.F ) return -1;
- if( A.S < B.S ) return +1;
- if( A.S > B.S ) return -1;
- if( LenA < LenB ) return +1;
- if( LenA > LenB ) return -1;
- return 0;
- }
- inline bool Cmp(const ii &a ,const ii &b){
- int Res = Calc(a ,b);
- if( Res == +1 ) return true;
- if( Res == -1 ) return false;
- if( a.F < b.F ) return true;
- if( a.F > b.F ) return false;
- if( a.S < b.S ) return true;
- if( a.S > b.S ) return false;
- return false;
- }
- int main()
- {
- n = (int)(s = Read() + ' ').size();
- scanf("%d" ,&q);
- for(int i = 0 ; i < q ; i++)
- {
- int L; scanf("%d" ,&L) ,L --;
- int R; scanf("%d" ,&R) ,R --;
- ii x = ii(L ,R);
- if( Cnt[x] == 0 ) Seg.push_back(x);
- Cnt[x] += 1;
- }
- Rank = ConstructSA(s ,n);
- sort(Seg.begin() ,Seg.end() ,Cmp); cout << endl;
- for(auto i : Seg) while( Cnt[i]-- ) printf("%d %d\n" ,i.F + 1 ,i.S + 1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement