题目传送门: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; }