Brief description :

后缀数组练习题系列啊啊，最长不重叠重复子串。

Analyse :

…

/*	
	Author : xiaodao
	Prob : POJ 1743. Musical Theme
	Status  : Accepted
	Last modify : GMT +8. Sept 16th 11:07
	Tags : Suffix Array
*/

#include 
#include 
#include 
#include 
using namespace std;

const int INF = 100000;
const int N = 20000, M = 88;
int SA[N], rank[N], height[N], key[N];
int A[N], C[N], t1[N+1], t2[N+1];
int n, m, ans;

void init(){
	int i, j, k, l, s; int *X = t1, *Y = t2; 
	for (i=0;i=0;i--) SA[--C[X[i]]] = i;
	
	X[n] = Y[n] = INF;
	
	for (l=1;l= l) Y[j++] = SA[i] - l;
		for (i=0;i=0;i--) SA[--C[key[i]]] = Y[i];
		
		swap(X, Y);
		X[SA[0]] = j = 0;
		for (i=1;i0) k--;
		if (rank[i]==0) height[0] = 0;
		else {
			j = SA[rank[i] - 1];
			while (A[i+k]==A[j+k]) k++;
			height[rank[i]] = k;
		}
	} 
}

bool f(int x){
	int l = SA[0], r = SA[0];
	for (int i=1;i= x) l = min(l, SA[i]), r = max(r, SA[i]);
		else {
			if (r-l >= x) return true;
			l = SA[i], r = SA[i];
		}
	}
	
	if (r-l >= x) return true;
	return false;
}


void solve(){
	
	if (!f(4)) ans = 0;
	else {
		int l=4, r=n/2, m;
		while (l>n && n!=0){
		init(); solve();
		cout << ans << endl;
	}	
}

Posted by xiaodao
Category: 日常