Tag: 最小表示法

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5442
数据生成器：http://paste.ubuntu.com/18084370/

这题，SA可做，SAM可做，最小表示法可做
然而我的SA对拍怎么都过不了，本地不错，交上去就wa，弃疗

#include<iostream>
#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 1600000+9;
const int SIGMA_SIZE = 30;

char pat[MAXN];
int n;

namespace Suffix_Array{
	#define SA Suffix_Array
	int sa[MAXN],height[MAXN],bot[MAXN];
	int t1[MAXN],t2[MAXN],*tmp,*rank;
	int m,cnt,Pos[MAXN],ord[MAXN],wor[MAXN];
	
	inline void GetHeight(){
		for (int i=1;i<=n;i++) height[i] = 0;
		for (int i=1;i<=n;i++) if (rank[i] > 1){
			int sta = max(0,height[rank[i-1]]-2);
			int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
			while (pat[p1++] == pat[p2++]) sta++;
			height[rank[i]] = sta;
		}
	}
	
	inline void build(){
		memset(bot,0,sizeof(bot));
		memset(height,0,sizeof(height));
		
		tmp = t1; rank = t2;
		n = strlen(pat+1); m = SIGMA_SIZE;
		for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+2]++;
		for (int i=2;i<=m;i++) bot[i] += bot[i-1];
		for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
		rank[sa[1]] = m = 1;
		for (int i=2;i<=n;i++)
			if (tmp[sa[i]]==tmp[sa[i-1]]) rank[sa[i]] = m;
			else rank[sa[i]] = ++m;
			
		for (int k=1;k<=n;k*=2){int T=0;
			for (int i=n-k+1;i<=n;i++) tmp[++T] = i;
			for (int i=1;i<=n;i++) if (sa[i]>k) tmp[++T] = sa[i]-k;
			for (int i=1;i<=m;i++) bot[i] = 0;
			for (int i=1;i<=n;i++) bot[rank[i]]++;
			for (int i=2;i<=m;i++) bot[i] += bot[i-1];
			for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
			
			swap(rank, tmp);
			rank[sa[1]] = m = 1;
			for (int i=2;i<=n;i++) if (tmp[sa[i]]==tmp[sa[i-1]] && tmp[sa[i]+k]==tmp[sa[i-1]+k]) rank[sa[i]] = m; else rank[sa[i]] = ++m; if (m >= n) break;
		}
		
		GetHeight();
	}
	
	inline bool sort_cmp(const int a, const int b){
		if (Pos[a] != Pos[b]) return Pos[a] < Pos[b];
		else return wor[a] < wor[b]; } inline bool judge(int i, int pos){ if ((pos>=1&&pos<=n/4) || (pos>=n/2+2&&pos<=n/2+n/4+1)){ cnt=1; if (pos>=1&&pos<=n/4) Pos[cnt]=pos, wor[cnt]=0; else Pos[cnt]=n/2+n/4+2-pos, wor[cnt]=1; while (height[i--] >= n/4){
				pos = sa[i];
				if (pos>=1&&pos<=n/4) Pos[++cnt]=pos, wor[cnt]=0; else if (pos>=n/2+2&&pos<=n/2+n/4-1) Pos[++cnt]=n/2+n/4+2-pos, wor[cnt]=1;
			}
			
			for (int j=1;j<=cnt;j++) ord[j] = j; sort(ord+1,ord+1+cnt,sort_cmp); printf("%d %d\n",Pos[ord[1]],wor[ord[1]]); return true; } else return false; } inline void solve(){ for (int i=n;i;i--) if (judge(i,sa[i])) break; } }; int main(){ int T; cin>>T;
	while (T--){
		scanf("%d%s",&n,pat+1); 
		for (int i=1;i<=n;i++) pat[n+i] = pat[i]; n *= 2;
		for (int i=1;i<=n;i++) pat[n+i+1] = pat[n-i+1];
		pat[n+1] = 'a'-1; n=n*2+1; pat[n+1] = 0;
		SA::build();
		SA::solve();
	}	
	return 0;
}