ZOJ 1729(Hidden Password-最小示意法)
ZOJ 1729(Hidden Password-最小表示法)#includecstdio#includecstdlib#includecstring#includeiost
ZOJ 1729(Hidden Password-最小表示法)
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<functional>#include<cmath>#include<cctype>#include<cassert>#include<climits>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,n) for(int i=n;i;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define RepD(i,n) for(int i=n;i>=0;i--)#define MEM(a) memset(a,0,sizeof(a))#define MEMI(a) memset(a,127,sizeof(a))#define MEMi(a) memset(a,128,sizeof(a))#define INF (2139062143)#define F (1000000009)#define MAXN (5000000+10)typedef long long ll;int T,n;char s[MAXN*2];int main(){ cin>>T; while (T--) { scanf("%d%s",&n,s+1); copy(s+1,s+1+n+1,s+n+1); int i=1,j=2; for(int k=0;k<=n&&i<=n&&j<=n;) { if (s[i+k]==s[j+k]) k++; else { if (s[i+k]>s[j+k]) i=i+k+1; else j=j+k+1; if(i==j) j++; k=0; } } cout<<min(i,j)-1<<endl; } return 0;}
