【BZOJ】1692- [Usaco2007 Dec]队列变换

【算法】字符串hash

【题解】

显然如果字母互不相同，贪心取是正确的。

如果存在字母相同，那么就换成比较后缀和前缀嘛。

但是要注意，不是后缀和前缀相同就能直接跳跃，每次必须只推一位。

取模的哈希比自然溢出慢了好多。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxn=30010,MOD=123456789,base=291;
ll sum1[maxn],sum2[maxn],p[maxn];
int n;
char c,s[maxn];
int calc1(int L,int R){return (sum1[R]+MOD-sum1[L-1]*p[R-L+1]%MOD)%MOD;}
int calc2(int L,int R){return (sum2[L]+MOD-sum2[R+1]*p[R-L+1]%MOD)%MOD;}
bool big(int L,int R){if(s[L]!=s[R])return s[L]>=s[R];int l=1,r=R-L+2;while(l<r){int mid=(l+r)>>1;if(calc1(L,L+mid-1)==calc2(R-mid+1,R))l=mid+1;else r=mid;}return s[L+l-1]>=s[R-l+1];
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){c=getchar();while(c<'A'||c>'Z')c=getchar();s[i]=c;}p[0]=1;for(int i=1;i<=n;i++)p[i]=p[i-1]*base%MOD;for(int i=1;i<=n;i++)sum1[i]=(sum1[i-1]*base+s[i]-'A')%MOD;for(int i=n;i>=1;i--)sum2[i]=(sum2[i+1]*base+s[i]-'A')%MOD;int L=1,R=n;for(int i=1,j=1;i<=n;i++,j++){if(!big(L,R)){putchar(s[L++]);}else{putchar(s[R--]);}if(j==80)putchar('
'),j=0;}return 0;
}