poj 1743 Musical Theme(文字列_接尾辞配列)

タイトルリンク:http://poj.org/problem?id=1743
1つのシーケンスを与えて、その中から1つのサブセグメントを選択することができて、このサブセグメントの各数に対してkを増加してあるいはkを減らす操作を行うことができて、サブセグメントの長さが5より大きくて、しかも2つのサブセグメントが重ならない最も長い繰り返しサブセグメントの長さを満たすのはいくらですか?
解題の考え方:この問題は接尾辞配列で解決できます.この問題を見ると接尾辞ツリーグループが考えられる.重複サブセグメント問題であるため、接尾辞配列は文字列問題だけでなく、他の重複サブセグメント問題もokであり、KMPも同様である.各サブセグメントがkを増加または減少させることができるので、x 1,y 1,x 2,y 2はx 1−y 1==x 2−y 2であれば一致(一致してから繰り返される)可能であると判断し、初期の長さnのシーケンスを長さn−1の差分シーケンスに変換する.
     前処理が終わると、sa配列、rank配列、height配列を求めることができます.これらはテンプレートをセットすることができます.自分で叩いてもいいです.私のように自分で叩いてもいいですが、断固として間違っています.処理後,理想状態はheight配列の最大値を探せばokであるが,理想は豊満であり,現実は骨感である.2つのサブセグメントが重ならないので、そうすることはできません.例を挙げると、22,22,22,22,9個2,最大のheight配列を探せば、答えは8で、華やかにWaを提出します.問題は,オーバーラップしない条件に合致する長さが5より大きい最大長を探すことに転化し,これは判定的な問題であり,0−−n/2内から最適解を二分検索で探すことができる.毎回mid=を算出する(maxx+minn)/2、さらにheightがmidより小さい接尾辞を排除し、heightがmidより大きい一陀接尾辞を残し、その最大の差を探してmidより大きいかどうかを判断すればよい.なぜこのように判断すればよいのか、まず考えてみると、heightがmidより小さい場合は、他の各接尾辞との最長共通接頭辞の長さがmidより小さく、これは条件に合わない.もう一つのheightはすべてmidより大きいmid、条件に合うかどうかはよくわかります.
テストデータ:
Input:
9 2 2 2 2 2 2 2 2 2
11 2 2 2 2 2 2 2 2 2 2 2
13 2 2 2 2 2 2 2 2 2 2 2 2 2
30 25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18 82 78 74 70 66 67 64 60 65 80
OutPut: 0 6 7 5
コード:

#include <stdio.h>
#include <string.h>
#define MAX 100000
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)


int n,arr[MAX];
int wa[MAX],wb[MAX];
int wv[MAX],wn[MAX];
int sa[MAX],rank[MAX],h[MAX];


int cmp(int *r,int a,int b,int l)  {   
    return r[a] == r[b] && r[a+l] == r[b+l];   
}  
void Da(int *r,int n,int m)   {  
    int i,j,k,p;           //p          
    int *x = wa,*y = wb,*t;//rank    x   
  
    // r    1           
    for (i = 0; i < m; ++i) wn[i] = 0;  
    for (i = 0; i < n; ++i) wn[x[i]=r[i]]++;  
    for (i = 1; i < m; ++i) wn[i] += wn[i-1];  
    for (i = n - 1; i >= 0; --i) sa[--wn[x[i]]] = i;  
  
    // r    j           
    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) wn[i] = 0;  
        for (i = 0; i < n; ++i) wn[wv[i]]++;  
        for (i = 1; i < m; ++i) wn[i] += wn[i-1];  
        for (i = n - 1; i >= 0; --i) sa[--wn[wv[i]]] = y[i];  
  
  
        t = x,x = y,y = t,p = 1;  
        for (x[sa[0]] = 0,i = 1; i < n; ++i)  
            x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p - 1: p++;  
    }  
}  
void Calheight(int *r,int n)   {  
    int i,j,k = 0;  
    for (i = 1; i <= n; ++i) rank[sa[i]] = i;    //sa   rank  
    for (i = 0; i < n; h[rank[i++]] = k)  
        for (k ? k--:0,j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);  
} 
int Solve(int n) {

	int i,j,k,ans = 0,flag;
	int minn,maxx,low,high,mid;//mid,minn maxx   ，low high sa  


	minn = 0,maxx = n / 2;
	while (minn <= maxx) {

		mid = minn + (maxx - minn) / 2;
		flag = 0,low = high = sa[1];
		for (i = 2; i <= n && !flag; ++i) {

			if (h[i] < mid) low = high = sa[i];
			else {

				low = min(low,sa[i]);
				high = max(high,sa[i]);
				if (high - low >= mid) flag = 1;
			}
		}
		if (flag) minn = mid + 1;
		else maxx = mid - 1;
	}


	return maxx >= 4 ? maxx + 1 : 0;
}


int main()
{
	int i,j,k,ans;


	while (scanf("%d",&n),n) {

		for (i = 0; i < n; ++i)
			scanf("%d",&arr[i]);
		for (i = 0; i < n - 1; ++i)
			arr[i] = (arr[i] - arr[i+1]) + 100;
		arr[n-1] = 0;


		Da(arr,n,200);
		Calheight(arr,n-1);
		ans = Solve(n-1);
		if (n < 10) printf("0
");
		else printf("%d
",ans);
	}
}

ZeroClockオリジナルですが、私たちは兄弟なので転載できます.