Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.
3 aaaa abab abcd
Case #1: 4 Case #2: 4 Case #3: 4
//
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
#include <stdio.h>
using namespace std;
#define two(i) (1<<(i))
const int MaxN = 200050;
int _;
typedef long long LL;
int wa[MaxN],wb[MaxN],wv[MaxN],ws[MaxN];
int saCmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void DA(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0; i<m; i++) ws[i]=0;
for(i=0; i<n; i++) ws[x[i]=r[i]]++;
for(i=1; i<m; i++) ws[i]+=ws[i-1];
for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i;
for(j=1,p=1; p<n; j*=2,m=p)
{
for(p=0,i=n-j; i<n; i++) y[p++]=i;
for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0; i<n; i++) wv[i]=x[y[i]];
for(i=0; i<m; i++) ws[i]=0;
for(i=0; i<n; i++) ws[wv[i]]++;
for(i=1; i<m; i++) ws[i]+=ws[i-1];
for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
x[sa[i]]=saCmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
int Rank[MaxN],height[MaxN];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1; i<=n; i++) Rank[sa[i]]=i;
for(i=0; i<n; height[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
return;
}
int ax[MaxN],sa[MaxN];
char s[MaxN];
int rmq[20][MaxN], mm[MaxN];
int query(int x, int y)
{
if(x>y)swap(x,y);
x++;
int L = y-x+1;
return min(rmq[mm[L]][x], rmq[mm[L]][y-(1<<mm[L])+1]);
}
void sol(int N)
{
int n = N*2+2;
for(int i = 0; i <= n; i++)rmq[0][i] = height[i];
for(int i = 1; i <= mm[n]; i++)
for( int j = 0; j <= n; j++ )
rmq[i][j] = min(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
LL ret = 0;
int pre1 = 0, pre2 = 0;
for(int i = 0; i <= n; i++)
{
int x = query(i, Rank[2*N+1-sa[i]]);
pre1 = min(pre1, height[i]);
ret += max(0, x-pre1);
pre1 = max(pre1, x);
x = query(i, Rank[2*N-sa[i]]);
pre2 = min(pre2, height[i]);
ret += max(0, x-pre2);
pre2 = max(pre2, x);
}
printf("Case #%d: %d\n", _++, ret);
}
void init()
{
mm[0] = -1;
for(int i = 1; i < MaxN; i++)
mm[i] = ((i & (i - 1))==0)? mm[i-1]+1 : mm[i-1];
}
int main()
{
_=1;
init();
int T;scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int n = strlen(s);
for(int i = 0; i < n; i++)
ax[i] = s[i]-'a'+1;
ax[n] = 27;
for(int i = n+1; i < 2*n+1; i++)
ax[i] = ax[2*n-i];
ax[2*n+1] = 0;
DA(ax, sa+1, 2*n+2, 28);
calheight(ax, sa, 2*n+2);
sol(n);
}
return 0;
}