最小标示法模板 poj1509

最小标示法:给定一个字符串,不断将其最后一个字符放到开头,最终会得到n个字符串,称这n个字符串循环同构,这些字符串中字典序最小的一个,就是最小表示法

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 1000005 int len;
int main(){
int t;
cin>>t;
while(t--){
char s[maxn<<]={};
cin>>(s+); len=strlen(s+);
for(int i=;i<=len;i++)
s[len+i]=s[i];
int j=,i=;
while(i<=len && j<=len){
int k=;
while(s[i+k]==s[j+k] && k<len)
k++;
if(s[i+k]>s[j+k])
i=i+k+;
else
j=j+k+;
if(i==j)j++;
}
cout<<min(i,j)<<'\n';
}
}

下面是进阶指南的模板

int n=strlen(s+);
for(int i=;i<=n;i++)s[n+i]=s[i];
int i=,j=,k;
while(i<=n && j<=n){
for(k=;k<=n;&&s[i+k]==s[j+k];k++);
if(k==n)break;
if(s[i+k]>s[j+k])
i=i+k+;
else j=j+k+;
if(i==j)j++;
}
ans=min(i,j);
上一篇:python 进阶读书笔记2 -- python魔法函数


下一篇:【读书笔记】iOS-网络-测试与操纵网络流量