OJ Board

Code: Select all

@ double the string -> str[] = "String""String"
@ i=0 j=1 k=0 len=str.length()
   while(i<len && j<len)
      # if(str[i+k] == str[j+k]) { k++; if(k==len) break; }
      # if(str[i+k] > str[j+k])  { i=i+k+1;  if(i<=j) i=j+1; k=0; }
      # if(str[i+k] < str[j+k])  { j=j+k+1; if(j<=i) j=i+1; k=0; }

   return Min(i,j)

Code: Select all

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				400006
#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 msg(x)			cout<<x<<endl;
#define EPS				1e-7
/*---- 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 ****************************/


#define LG 21
char A[LMT];
struct entry {
	int nr[2], p;
} L[LMT] , T[ LMT ];
int P[LG][LMT], N, i, stp, cnt;
int counterAray[LMT];
int prefixArray[LMT];

int cmp(struct entry a, struct entry b)
{
	return a.nr[0] == b.nr[0] ? (a.nr[1] < b.nr[1] ? 1 : 0) : (a.nr[0] < b.nr[0] ? 1 : 0);
	
}

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(counterAray ,0, (iM + 1) * sizeof(int));
	for(int i = 0 ; i< len; i ++ ) {
		counterAray[v[i].nr[index] + 1] ++;
	}
	
	prefixArray[0] = counterAray[0];
	for(int i = 1 ; i <= iM /* IM */ ; i ++ ) {
		prefixArray[i] = counterAray[i] + prefixArray[i-1];
	}
	
	for (int i = len - 1; i >=0 ; i -- ) {
		prefixArray[v[i].nr[index] + 1] --;
		
		if( prefixArray[v[i].nr[index] + 1] < 0 ) {
			printf("ARRAY LESS\n");
		}
		T[prefixArray[v[i].nr[index] + 1]] = v[i];
	}
	
	for(int i = 0 ;i <len; i ++ ) v[i] = T[i];
	
}
void buildSA()
{
	
	for (N = strlen(A), i = 0; i < N; i ++)
		P[0][i] = A[i] - 'a';
	for (stp = 1, cnt = 1; cnt >> 1 < N; stp ++, cnt <<= 1)
	{
		for (i = 0; i < N; i ++)
		{
			L[i].nr[0] = P[stp - 1][i];
			L[i].nr[1] = i + cnt < N ? P[stp - 1][i + cnt] : -1;
			L[i].p = i;
		}
		//countingSort(L , 1 , N);
		//countingSort(L , 0 , N );
		
		sort(L, L + N , cmp);
		for (i = 0; i < N; i ++)
			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;
		
		
	}
}

int lcp(int x, int y)
{
	int k, ret = 0;
	if (x == y) return N - x;
	for (k = stp - 1; k >= 0 && x < N && y < N; k --){
		
		if( k >= LG ) {
			printf("LHSLHDD\n");
		}
		if (P[k][x] == P[k][y])
			x += 1 << k, y += 1 << k, ret += 1 << k;
	}
	return ret;
	
}

int main()
{
	int tc;
	
	//freopen("in.txt", "r", stdin);
	sc(tc);
	
	while (tc -- ) {
		scanf("%s",A);
		strcat(A, A );
		
		buildSA();
		int ans = -1;
		for(int i = 0; i < N -1  ; i ++ ) {
			if(L[i].p < N/2 ) {
				if(ans ==-1 ) ans = L[i].p;
				
				if(lcp( ans ,  L[i + 1].p ) >= N / 2 ) {
					if( ans > L[i+1]. p ) ans = L[i+1].p;
				}
			}
		}
		
		printf("%d\n", ans + 1 );
	}
}