#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 600005
int N;
int R[MAXN],SA[MAXN],lcp[MAXN];
char A[MAXN];
void Manachers()
{
int r = 0, p = 0;
for (int i=1;i<=N;i++){
if (i <= r) R[i] = min(R[2*p-i],r-i);
else R[i] = 0;
while (i > R[i] && A[i-R[i]-1] == A[i+R[i]+1]) R[i]++;
if (r < i+R[i]) r = i+R[i], p = i;
}
}
void SuffixArray()
{
int i,j,k;
int m = 27;
vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0);
for (i=1;i<=N;i++) cnt[x[i] = (A[i]=='#')?27:A[i]-'a'+1]++;
for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
for (i=N;i;i--) SA[cnt[x[i]]--] = i;
for (int len=1,p=1;p<N;len<<=1,m=p){
for (p=0,i=N-len;++i<=N;) y[++p] = i;
for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
for (i=0;i<=m;i++) cnt[i] = 0;
for (i=1;i<=N;i++) cnt[x[y[i]]]++;
for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i];
swap(x,y); p = 1; x[SA[1]] = 1;
for (i=1;i<N;i++)
x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
}
}
void LCP()
{
int i,j,k=0;
vector <int> rank(N+1,0);
for (i=1;i<=N;i++) rank[SA[i]] = i;
for (i=1;i<=N;lcp[rank[i++]]=k)
for (k?k--:0,j=SA[rank[i]-1];A[i+k]==A[j+k];k++);
}
int main()
{
int i;
scanf("%s",A+1); N = strlen(A+1);
for (i=N;i;i--) A[i+i-1] = A[i]; N = N+N-1;
for (i=2;i<N;i+=2) A[i] = '#';
Manachers(); SuffixArray(); LCP();
for (i=1;i<=N;i++){
puts(A+SA[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
8856 KB |
Output isn't correct - wrong output format : a is not a valid integer |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
