题解 P1368 【工艺 /【模板】最小表示法】

Huah · 2020-09-04 20:22:38 · 题解

1.问题描述

给出一个长度为n的字符串S，其第i个字符为S_i(0<=i<n)。 可以重复执行操作：移除第0个字符，并将其插入到第n-1个位置。 找出所有可以通过上述操作得到的字符串中字典序最小的字符串，这个字典序最小的字符串被称为字符串S的最小表示。

2.算法流程

1.定义两个指针i,j，定义变量k，初始时，让i指向位置0，j指向位置1，k=0。

2.比较第i+k和第j+k个字符， （这里默认为x+k为(x+k)\mod n，x=i,j）

若S_{i+k}=S_{j+k}，让k=k+1。

若S_{i+k}>S_{j+k}，让i=i+k，k=0。

若S_{i+k}<S_{j+k}，让j=j+k，k=0。

3.若i=j，让i=i+1

4.若i>=n||j>=n||k>=n，min(i,j)即为字典序最小的字符串的开头。否则，回到2。

3.证明

1.当k=n，因为算法保证i!=j，则可以证明字符串只由一个字符组成，那么任意i,j都为最小表示。

2.当S_{i+k}!=S_{j+k}，不妨假设S_{i+k}>S_{j+k}，则第i,i+1,...,i+k个位置一定不是字典序最小的字符串，设第p个位置为最小字符串(i<=p<=i+k)，则有

在j,j+1,...,j+k中存在对应比其字典序更小的字符串。

3.又i,j会把所有下标都扫描到，当i>=n||j>=n又必有i,j中某个指针的值小于n，而另一指针一定由于操作2或操作3而移动，故值小于n的指针则为最小表示字符串的开头。

4.复杂度

时间复杂度O(n)，空间复杂度O(n)，证明略。

5.代码

P1368 工艺 /【模板】最小表示法

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,a[N];
int sol(int n,int a[N])
{
    if(n==1) return 0;
    int i=0,j=1,k=0;
    while(i<n&&j<n&&k<n)
    {
        if(i==j) i++;
        else if(a[(i+k)%n]==a[(j+k)%n]) k++;
        else if(a[(i+k)%n]>a[(j+k)%n]) i+=k+1,k=0;
        else j+=k+1,k=0;
    }
    return min(i,j);
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int ans=sol(n,a);
    for(int i=0;i<n;i++)
        printf(i==n-1?"%d\n":"%d ",a[(i+ans)%n]);
}