HDU 5442 Favorite Donut
第一种方法,最小表示法
其实呢,你将每一个字母反转一下,将’a’变成’z’,就是最小表示法。
但是反转之后,我们如果用最小表示法,得到的是,在原串上位置最靠后的情况,与题意不服,所以我这里就强行将之往后硬判,最坏复杂度是当串所以的字符都相同的情况,退化成O(n2)。
// whn6325689
// Mr.Phoebe
// http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<50
#define speed std::ios::sync_with_stdio(false);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1;
char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=20010;
char str[MAXN],rev[MAXN];
int n,ch[30];
int init()
{
int now='z';
for(int i=0; i<26; i++)
ch[i]=now--;
}
int getsmall(string s, bool flag)
{
int i,j,k,l;
int N=s.length();
s+=s;
int ans=0;
for(i=0,j=1; j<N;)
{
for(k=0; k<N&&s[i+k]==s[j+k]; k++);
if(k>=N)
{
if(flag)
{
ans=j;
j++;
continue;
}
break;
}
if(s[i+k]<s[j+k])
{
j+=k+1;
}
else
{
l=i+k;
i=j;
ans=i;
j=max(l,j)+1;
}
}
return ans;
}
bool compare(int ans0,int ans1)
{
int pos1=ans0,pos2=ans1;
for(int i=0; i<n; i++)
{
if(str[pos1]==str[pos2])
{
if(++pos1>=n) pos1-=n;
if(--pos2<0) pos2+=n;
}
else
{
return str[pos1]>str[pos2];
}
}
return ans0<=ans1;
}
string st,en;
int main()
{
// freopen("data.txt", "r", stdin);
init();
int T;
read(T);
while(T--)
{
st.clear();
en.clear();
read(n);
scanf("%s",str);
for(int i=0; i<n; i++)
st+=ch[str[i]-'a'];
en=st;
reverse(en.begin(),en.end());
int ans0=getsmall(st,false);
int tmp=getsmall(en,true);
int ans1=(n-tmp-1)%n;
if (compare(ans0,ans1))
printf("%d 0\n",ans0+1);
else
printf("%d 1\n",ans1+1);
}
return 0;
}
后缀数组法,裸的后缀数组应用
// xixihaha
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;
#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
template<class T>
inline bool read(T &n)
{
T x = 0, tmp = 1;
char c = getchar();
while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
if(c == EOF) return false;
if(c == '-') c = getchar(), tmp = -1;
while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
n = x*tmp;
return true;
}
template <class T>
inline void write(T n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
int len = 0,data[20];
while(n)
{
data[len++] = n%10;
n /= 10;
}
if(!len) data[len++] = 0;
while(len--) putchar(data[len]+48);
}
//-----------------------------------
const int MAXN=100010;
char C[MAXN],rC[MAXN];
int idx[MAXN],mp[MAXN];
int rk[MAXN],sa[MAXN],height[MAXN],w[MAXN],wa[MAXN],ret[MAXN];
void getSa (int len,int up)
{
int *k = rk;
int *id = height;
int *r = ret;
int *cnt = wa;
for(int i=0;i<up;i++) cnt[i] = 0;
for(int i=0;i<len;i++) cnt[k[i] = w[i]]++;
for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
for(int i = len - 1; i >= 0; i--) {
sa[--cnt[k[i]]] = i;
}
for(int d = 1,p = 0; p < len;){
for(int i = len - d; i < len; i++) id[p++] = i;
for(int i=0;i<len;i++)if(sa[i] >= d) id[p++] = sa[i] - d;
for(int i=0;i<len;i++) r[i] = k[id[i]];
for(int i=0;i<up;i++) cnt[i] = 0;
for(int i=0;i<len;i++) cnt[r[i]]++;
for(int i=0;i<up;i++) cnt[i+1] += cnt[i];
for(int i = len - 1; i >= 0; i--) {
sa[--cnt[r[i]]] = id[i];
}
swap(k,r);
p = 0;
k[sa[0]] = p++;
for(int i=0;i<len-1;i++) {
if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d])
k[sa[i+1]] = p - 1;
else k[sa[i+1]] = p++;
}
if(p >= len) return ;
d *= 2,up = p, p = 0;
}
}
void getHeight(int len) {
for(int i=0;i<len;i++) rk[sa[i]] = i;
height[0] = 0;
for(int i = 0,p = 0; i < len - 1; i++) {
int j = sa[rk[i]-1];
while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) {
p++;
}
height[rk[i]] = p;
p = max(0,p - 1);
}
}
int getSuffix(char s[]) {
int len = strlen(s),up = 0;
for(int i = 0; i < len; i++) {
w[i] = s[i];
up = max(up,w[i]);
}
w[len++] = 0;
getSa(len,up+1);
getHeight(len);
return len;
}
int solve(char s[],int n)
{
int len=getSuffix(s);
/* for(int i=1;i<len;i++){ printf("%s\n",s+sa[i]); }*/
int start=len-1;
while(sa[start]>n/2)start--;
int ans=idx[sa[start]];
while(height[start]>=n/2){
start--;
ans=min(ans,idx[sa[start]]);
}
return ans;
}
int cmp(int x,int y,int n)
{
for(int i=x,j=y,k=0;k<n;k++,i++,j++){
if(C[i]==rC[j])continue;
if(C[i]<rC[j])return -1;
if(C[i]>rC[j])return 1;
}
return 0;
}
int main()
{
// freopen("in","r",stdin);
int T;scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
scanf("%s",C);
for(int i=0;i<n;i++)rC[i]=C[i];
reverse(rC,rC+n);
for(int i=0;i<n;i++){
C[i+n]=C[i];
idx[i]=idx[i+n]=i;
}
C[n*2]='\0';
int ans=solve(C,n*2),dir=0;
for(int i=0;i<n;i++){
rC[i+n]=rC[i];
idx[i]=idx[n+i]=n-i-1;
mp[n-i-1]=i;
}
rC[n*2]='\0';
// cout<<rC<<endl;
int res=solve(rC,n*2);
// cout<<ans<<"!!"<<res<<endl;
// cout<<string(C+ans,n)<<endl;
// cout<<string(rC+mp[res],n)<<endl;
int flag=cmp(ans,mp[res],n);
if(flag==-1){
ans=res,dir=1;
}
else if(flag==0){
if(res<ans){
ans=res;
dir=1;
}
}
printf("%d %d\n",ans+1,dir);
}
return 0;
}
还没有评论,来说两句吧...