poj 3693 Maximum repetition substring (後綴數組)

題意：求一個字符串中，能由單位串repeat得到的子串中，單位串重復次數最多的子串。若有多個重復次數相同的，輸出字典序最小的那個。

解題思路：其實跟論文差不多，我看了很久沒看懂，後來總算理解了一些。假設我們的單位串長度為l，那麼我們將串劃分為s[0] , s[l] , s[2*l] , s[3*l]。。這樣，可以根據l劃分為n/l段。枚舉一個j，表示當前枚舉的位置為s[j*l]，我們要做的是，求suf[j*l]跟suf[(j+1)*l]的lcp  （這裡用rmq做，詢問是o(1)的），假設這個lcp是k，那我們知道，從s[j*l]開始的，以l為單位長度的repeat次數至少是k/l + 1，這是為什麼呢？想想lcp的意思，應該能想通的。但這樣並不一定是最優的，因為我們如果往前推，有可能還有一些是相同的，那就往前枚舉i，表示前i個也是相同的，一直枚舉到不同，或者額外增加的長度超過l為止（超過l就相當於是上一個j了）。這時，我們的新的lcp長度k=k+i了，用這個k去計算repeat次數才是正確的。遍歷過程中，我們要把取到最大repeat次數的l記下來，求字典序最小時，就按rank從小到大枚舉開頭，然後看有沒有記下的l中，在當前開頭的字符串是符合最大repeat次數的（用lcp再判斷一次好了），一旦找到符合的，就輸出好了。

沒寫case，一直錯，一直找不到錯哪兒，淚奔了。。。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std ;
const int maxn = 511111 ;

int p[maxn] ;
int min ( int a , int b ) { return a < b ? a : b ; }
int dp[25][maxn] , f[maxn] , ans , fuck ;

vector<int>vec ;
struct Suf{
	int wa[maxn] , wb[maxn] , ws[maxn] , wv[maxn] ;
	int rank[maxn] , hei[maxn] , sa[maxn] ;

	int cmp ( int *r , int i , int j , int l ){ return r[i] == r[j] && r[i+l] == r[j+l] ; }

	void da ( int *r , int n , int m ){
 	   	int *x = wa , *y = wb , *t ;
		int i , j , k , p ;
		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 < m ; i ++ ) ws[i] = 0 ;
			for ( i = 0 ; i < n ; i ++ ) ws[x[i]] ++ ;
			for ( i = 1 ; i < m ; i ++ ) ws[i] += ws[i-1] ;
			for ( i = n - 1 ; i >= 0 ; i -- ) sa[--ws[x[y[i]]]] = y[i] ;
			for ( t = x , x = y , y = t ,x[sa[0]] = 0 , p = 1 , i = 1 ; i < n ; i ++ )
				x[sa[i]] = cmp ( y , sa[i-1] , sa[i] , j ) ? p - 1 : p ++ ;
		}
		k = 0 ;
		for ( i = 1 ; i < n ; i ++ ) rank[sa[i]] = i ;
		for ( i = 0 ; i < n - 1 ; hei[rank[i++]] = k )
			for ( k ? k -- : 0 , j = sa[rank[i]-1] ; r[i+k] == r[j+k] ; k ++ ) ;
	}

	void rmq ( int n ) {
		int i , j ;
		for ( i = 1 ; i <= n ; i ++ ) dp[0][i] = hei[i] ;
		for ( i = 1 ; i <= 20 ; i ++ )
			for ( j = 1 ; j + ( 1 << i ) - 1 <= n ; j ++ )
				dp[i][j] = min ( dp[i-1][j] , dp[i-1][j+(1<<(i-1))] ) ;
	}

	int query ( int l , int r ) {
		if ( l > r ) swap ( l , r ) ;
		l ++ ;//要從height[l+1]到height[r]之間求最小值
		if ( l == r ) return dp[0][l] ;
		int k = r - l + 1 ;
		return min ( dp[f[k]][l] , dp[f[k]][r-(1<<f[k])+1] ) ;
	}

	void solve ( int n , char *s ) {
		rmq ( n ) ;
		int i , j , k , l , r ;
		for ( l = 1 ; l < n ; l ++ )
			for ( j = 0 ; j < n / l ; j ++ ) {
				int pos1 = j * l , pos2 = j * l + l ;
				k = query ( rank[pos1] , rank[pos2] ) ;
				i = 0 ;
				if ( j != 0 ) {
					while ( i < l && s[pos1-i-1] == s[pos2-i-1] ) i ++ ;
				}
				k += i ;
				int add = k / l + 1 ;
				if ( add == ans ) vec.push_back ( l ) ;
				if ( add > ans ) {
					ans = add ;
					vec.clear () ;
					vec.push_back ( l ) ;
				}
			}
		int flag ;
		for ( i = 1 ; i <= n ; i ++ ) {
			flag = 0 ;
			for ( j = 0 ; j < vec.size () ; j ++  ) {
				l = vec[j] ;
				k = query ( i , rank[sa[i]+l] ) ;
				if ( k / l + 1 == ans ) {
					for ( r = 0 ; r < ans * l ; r ++ )
						printf ( "%c" , s[sa[i]+r] ) ;
					puts ( "" ) ;
					flag = 1 ;
					break ;
				}
			}
			if ( flag ) break ;
		}
	}

} arr ;

char s1[maxn] ;
int s[maxn] ;

int main () {
	int cas , n , i , j , ca = 0 ;
	j = 0 ;
	for ( i = 1 ; i < maxn - 1111 ; i ++ ) {
		if ( i > 1 << j + 1 ) j ++ ;
		f[i] = j ;
	}
	scanf ( "%d" , &cas ) ;
	while ( cas -- ) {
		scanf ( "%s" , s1 ) ;
		if ( s1[0] == '#' ) break ;
		vec.clear () ;
		ans = 1 ;
		n = strlen ( s1 ) ;
		int len = 0 ;
		for ( i = 0 ; i < n ; i ++ ) s[i] = s1[i] ;
		s[n] = 0 ;
		arr.da ( s , n + 1 , 555 ) ;
		printf ( "Case %d: " , ++ca ) ;
		arr.solve ( n , s1 ) ;
	}
}