Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(v) (v).begin(),(v).end()
- #define INF int(1e8)
- #define NINF int(-1e8)
- #define clr(a,v) memset(a,v,sizeof(a))
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define eps 1e-8
- #define PI acos(-1)
- #define MOD (ll)(1e9 + 7)
- #define readFile freopen("in.txt","r",stdin)
- #define fastIO ios::sync_with_stdio(0)
- using namespace std;
- int const N = 100010;
- int sufArr[N], tmpSufArr[N], rank[N], tmpRank[N], lcp[N], n;
- char text[N];
- void radixSort(int k){
- int freq[N] = {0}, acum = 0, mx = max(300,n);
- for(int i = 0; i < n; i++) freq[i+k < n ? rank[i+k] : 0]++;
- for(int i = 0; i < mx; i++){
- int t = freq[i]; freq[i] = acum;
- acum += t;
- }
- for(int i = 0; i < n; i++) tmpSufArr[freq[sufArr[i]+k < n ? rank[sufArr[i]+k] : 0]++] = sufArr[i];
- for(int i = 0; i < n; i++) sufArr[i] = tmpSufArr[i];
- }
- void buildSuffixArray(){
- clr(sufArr,0); clr(tmpSufArr,0); clr(rank,0), clr(tmpRank,0);
- for(int i = 0; i < n; i++) sufArr[i] = i, rank[i] = text[i];
- for(int k = 1; k <= n; k <<= 1){
- radixSort(k);
- radixSort(0);
- int r = 0;
- tmpRank[sufArr[0]] = 0;
- for(int i = 1; i < n; i++){
- if(rank[sufArr[i]] == rank[sufArr[i-1]] && rank[sufArr[i]+k] == rank[sufArr[i-1]+k])
- tmpRank[sufArr[i]] = r;
- else tmpRank[sufArr[i]] = ++r;
- }
- for(int i = 0; i < n; i++) rank[i] = tmpRank[i];
- if(rank[sufArr[n-1]] == n-1) break;
- }
- }
- void buildLcp(){
- clr(lcp,0);
- int pos[N] = {0}, plcp[N]= {0}, l = 0;
- pos[sufArr[0]] = -1;
- for(int i = 1; i < n; i++) pos[sufArr[i]] = sufArr[i-1];
- for(int i = 0; i < n; i++){
- if(pos[i]==-1){
- plcp[i] = 0;
- continue;
- }
- while(text[i+l] == text[pos[i]+l] && i+l < n) l++;
- plcp[i] = l;
- l = max(l-1,0);
- }
- for(int i = 0; i < n; i++) lcp[i] = plcp[sufArr[i]];
- }
- pair<int,int> match(int idx, int len){
- int l = 0, r = n-1;
- pair<int,int> res;
- while(l < r){
- int mid = (l+r)>>1;
- int ans = strncmp(text+sufArr[mid],text+sufArr[idx],len);
- if(ans >= 0) r = mid;
- else l = mid+1;
- }
- res.first = l;
- l = 0; r = n-1;
- while(l < r){
- int mid = (l+r)>>1;
- int ans = strncmp(text+sufArr[mid],text+sufArr[idx],len);
- if(ans > 0) r = mid;
- else l = mid+1;
- }
- if(strncmp(text+sufArr[r],text+sufArr[idx],len)) r--;
- res.second = r;
- return res;
- }
- int main(){
- #ifndef ONLINE_JUDGE
- readFile;
- #endif
- int t; scanf("%d",&t);
- while(t--){
- scanf("%s",text);
- // strcat(text,"$");
- n = strlen(text);
- buildSuffixArray();
- buildLcp();
- int mx = 0, idx = -1;
- for(int i = 1; i < n; i++){
- if(lcp[i] > mx) mx = lcp[i], idx = i;
- }
- if(!mx){
- printf("No repetitions found!\n");
- continue;
- }
- pair<int,int> oc = match(idx-1,mx);
- for(int i = sufArr[idx]; i < sufArr[idx]+mx; i++) printf("%c",text[i]);
- printf(" %d\n",oc.second-oc.first+1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement