I am using sorting The string lexicographically
My programs outputs correct for small input..
Code: Select all
//
// main.cpp
// 11732 - "strcmp()" Anyone?
//
// Created by Repon Macbook on 4/3/15.
// Copyright (c) 2015 Repon Macbook. All rights reserved.
//
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 5005
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define debug(x) cout <<#x <<" -> " << x << endl;
#define EPS 1e-7
#define fred() freopen("in.txt","r",stdin);
#define fwrt() freopen("in.txt","w",stdout);
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
class SUF_ARA{
public:
#define LG LMT
char A[LMT][1005];
struct entry {
int nr[2], p;
} L[LMT] , T[ LMT ];
int P[LG][LMT], N, i, stp, cnt;
int lcpAr[LMT];
int CT[LMT];
int PFA[LMT];
int maxlen;
int cmp(struct entry a, struct entry b)
{
if( a.nr[0] == b.nr[0] && b.nr[1] == a.nr[1]) return 0;
return 1;
}
void countingSort (entry v[] , int index , int len )
{
int iM = -100;
for(int i = 0 ; i < len ; i ++ ){
iM = max(iM , v[i].nr[index] + 1);
}
memset(CT ,0, (iM + 1) * sizeof(int));
for(int i = 0 ; i< len; i ++ ) {
CT[v[i].nr[index] + 1] ++;
}
PFA[0] = CT[0];
for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
PFA[i] = CT[i] + PFA[i-1];
}
for (int i = len - 1; i >=0 ; i -- ) {
PFA[v[i].nr[index] + 1] --;
T[PFA[v[i].nr[index] + 1]] = v[i];
}
for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
}
void buildSA()
{
//N = strlen(A); // N is global
for(int i = 0 ; i < N ; i ++ ) P[0][i] = A[i][0];
for (stp = 1, cnt = 1; cnt <= maxlen ; stp ++, cnt ++)
{
for (i = 0; i < N; i ++)
{
L[i].nr[0] = P[stp - 1][i];
L[i].nr[1] = ( A[i][cnt] );
L[i].p = i;
}
countingSort(L , 1 , N);
countingSort(L , 0 , N );
//sort(L, L + N , cmp);
P[stp][L[0].p] = 0;
int id = 1;
for (i = 1; i < N; i ++){
int res = cmp (L[i], L[i-1]);
if(res) P[stp][L[i].p] = id ++;
else P[stp][L[i].p] = id ++;
//P[stp][L[i].p] = i > 0 && L[i].nr[0] == L[i - 1].nr[0] && L[i].nr[1] == L[i - 1].nr[1] ? P[stp][L[i - 1].p] : i;
}
//if(id == N ) break;
}
L[N].p = N;
}
int lcp(int x, int y)
{
int ret = 0;
int i;
for( i = 0 ; A[x][i] || A[y][i] ; i++ ) {
if( A[x][i] != A[y][i]) return 2 * ret + 1;
ret ++;
}
return 2 * (ret + 1) ;
// else return 2* ret + 1;
}
void buildLCP()
{
for(int i = 0; i < N-1 ; i ++) {
lcpAr[i] = lcp(L[i].p, L[i+1].p);
//debug(lcpAr[i]);
}
}
};
SUF_ARA sf;
int main()
{
int n ,cs = 0;
freopen("in.txt", "r", stdin);
while (1) {
sc(n);
if(n==0) break;
sf.maxlen = 0;
for( int i = 0; i < n ; i ++) {
scanf("%s",sf.A[i]);
sf.maxlen = max( sf.maxlen , (int) strlen(sf.A[i]));
}
sf.N = n;
sf.buildSA();
sf.buildLCP();
ll ans = 0;
int cnt = 0;
for(int i = 0 ; i < n ; i ++ ) {
int iM = inf ;
for (int j = i + 1 ; j < n ; j ++ ) {
iM = min(iM , sf.lcpAr[j-1]);
//debug(iM);
ans += iM;
cnt ++;
}
}
printf("Case %d: %lld\n" , ++cs, ans);
}
return 0;
}