题解：P13270 【模板】最小表示法

· · 题解

最小表示法竟然更新模板题了！

那我就要来写题解了。

暴力解法

枚举循环同构串的第一个位置，然后暴力用字符串挨个比较的方法比较。

时间复杂度 O(n^2) 获得 30 分。

优化解法

考虑如何优化暴力解法。

首先，这循环同构看起来有点烦，所有我们选择复制一份到字符串后面。

然后再考虑如何快速进行字符串比较。

首先字符串比较需要找到字符串第一个不相等的位置。

这里我们可以用前缀哈希 + 二分 / 倍增的方式。

就可以 O(n\log n) 获得 50 分。

代码如下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7+10;
int n;
string s;
unsigned int h[maxn],p[maxn];
unsigned int gethash(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s,s=" "+s+s;
    p[0]=1;
    for(int i=1;i<=2*n;i++) h[i]=h[i-1]*131+s[i],p[i]=p[i-1]*131;
    int st=1;
    for(int i=2;i<=n;i++){
        int ans=-1;
        for(int p=30;p>=0;p--){//利用哈希比较字符串 
            if(ans+(1<<p)>n) continue;
            if(gethash(st,st+ans+(1<<p))==gethash(i,i+ans+(1<<p))) ans+=(1<<p);
        }
//      cout<<ans<<'\n';
        if(ans!=n) if(s[i+ans+1]<s[st+ans+1]) st=i;
    }
    for(int i=st;i<=st+n-1;i++) cout<<s[i];
    return 0;
}

暴力的优化解法

算法介绍

这里我们尽量尝试去排除更多的无效状态

假设我们现在要比较第 st 位开头和第 i 开头的指针。

我们暴力找到一个 j<n 使得 st 到 st+j-1 位与 i 到 i+j-1 位完全相等。

如果没找到一个合适的 j，那么我们易证，字符串内所有字符都相等。

如果 st+j 位比第 i+j 位更优，说明对于任意 0\le k\le j，以 i+k 开头的表示都不可能成为最优解。

因为对于一个 i+k，st+k 一定比它更优，如下图。

这时，i 就可以直接跳到 i+j+1 了。

如果 i 更优，我们就可以直接更新最优解并跳到 \max(i+1,st+j+1) 了。（我不会告诉你这里只跳到 i+1 能撞过去还跑得飞快并且时间复杂度不正确）

然后做完了？做完了。

代码时间

代码十分简短。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e7;
int n;
string s;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s,s=" "+s+s;
    int st=1;
    for(int i=2;i<=n;){
        int j=0;
        for(j=0;j<n && s[st+j]==s[i+j];j++);
        if(j==n) break;
        if(s[st+j]>s[i+j]){
            int m=st;
            st=i,i=max(i+1,m+j+1);
        }
        else i+=j+1;
    }
    for(int i=st;i<=st+n-1;i++) cout<<s[i];
    return 0;
}

时间复杂度证明

对于 st+j 位比 i+j 位更优的情况，通过 O(j) 的枚举使 i 前进了 j 步，因为 i 最多移动 n 步，所以时间复杂度均摊 O(n)。

对于另一种情况，i 和 st 总共移动了至少 j 步，而 st 和 i 都最多移动 n 步，所以均摊时间复杂度 O(n)。

所以总复杂度 O(n)，可以过这道题。