BZOJ_2882_工艺
给出一个字符串，求与它循环同构的串中字典序最小的串。
后缀数组/后缀自动机+map 都可以在O(nlogn)的时间复杂度求出。
实际上有一个专门解决这类问题的算法：最小表示法。
首先把串复制一遍贴在原串后面，这样每个循环同构的串可以用S[i]~S[i+n-1]来表示，设为w(i)。
也就是说我们把所有的串拿出来了，比较就行了。
在比较w(i)和w(j)时的最坏时间复杂度是O(n)的，也就是说这只是一个暴力的做法。
实际上我们不需要对所有的w(i)都进行一次比较。
假设比较w(i)和w(j)时比较了k个字符，直到k+1个字符不同。
那么我们将字典序大的那边指针向后跳k+1即可，因为已经知道有比这些串小的串了(就在另一个指针的后面)
相当于每个指针最多向后跳n次，复杂度就变成O(n)的了，非常好写。
代码：
while(i<=n&&j<=n) {
for(k=0;k<n&&w[i+k]==w[j+k];k++);
if(k==n) break;
if(w[i+k]>w[j+k]) {
i+=k+1; if(i==j) i++;
}else {
j+=k+1; if(i==j) j++;
}
}
i=min(i,j);
BZOJ_2882代码：
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
char pbuf[10000000] , *pp = pbuf;
inline void write(int x)
{
static int sta[35];
int top = 0;
if(!x)sta[++top]=0;
while(x) sta[++top] = x % 10 , x /= 10;
while(top) *pp ++ = sta[top -- ] ^ '0';
}
#define N 600050
int w[N],n;
int main() {
n=rd();
register int i;
for(i=1;i<=n;i++) w[i]=rd(),w[i+n]=w[i];
register int j=2,k; i=1;
while(i<=n&&j<=n) {
for(k=0;k<n&&w[i+k]==w[j+k];k++);
if(k==n) break;
if(w[i+k]>w[j+k]) {
i+=k+1; if(i==j) i++;
}else {
j+=k+1; if(i==j) j++;
}
}
i=min(i,j);j=i+n-1;
while(i<=j) write(w[i]),*pp++=' ',i++;
fwrite(pbuf,1,pp-pbuf,stdout);
return 0;
}
BZOJ_1398_Vijos1382寻找主人 Necklace
题意：判断两个串是否循环同构。
分析：分别求两个串的最小表示，然后比较即可，时间复杂度O(n)。
代码：
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2000050
int n;
int a[1000050];
char w[N];
int main() {
int i;
scanf("%s",w+1);
int n=strlen(w+1);
for(i=1;i<=n;i++) w[i+n]=w[i];
int j=2,k; i=1;
while(i<=n&&j<=n) {
for(k=0;k<n&&w[i+k]==w[j+k];k++) ;
if(k==n) break;
if(w[i+k]>w[j+k]) {
i+=k+1; if(i==j) i++;
}else {
j+=k+1; if(i==j) j++;
}
}
i=min(i,j);
for(k=1;k<=n;k++) a[k]=w[i+k-1];
scanf("%s",w+1);
if(strlen(w+1)!=n) {
puts("No"); return 0;
}
for(i=1;i<=n;i++) w[i+n]=w[i];
j=2;i=1;
while(i<=n&&j<=n) {
for(k=0;k<n&&w[i+k]==w[j+k];k++) ;
if(k==n) break;
if(w[i+k]>w[j+k]) {
i+=k+1; if(i==j) i++;
}else {
j+=k+1; if(i==j) j++;
}
}
i=min(i,j);
for(k=1;k<=n;k++) if(a[k]!=w[i+k-1]) {
puts("No"); return 0;
}
puts("Yes");
for(i=1;i<=n;i++) printf("%c",a[i]);
}
总结(来自周源《浅析“最小表示法”思想在字符串循环同构问题中的应用》，我认为说得很好):
“最小表示法”是判断两种事物本质是否相同的一种常见思想，它的通用性也是被人们认可的——无论是搜索中判重技术，还是判断图的同构之类复杂的问题，它都有着无可替代的作用。仔细分析可以得出，其思想精华在于引入了“序”这个概念，从而将纷繁的待处理对象化为单一的形式，便于比较。