牛客 - 挑战赛39B 密码系统

传送门：牛客 - 挑战赛39B

思路分析

处理环状问题，一般先将原串复制一倍
这样每种划分方案就变成从第i个为起点后面每k个字符
那么就可以处理出每一个起点所包含的字符串中字典序最大的子串
判断两个字符串大小可以通过二分找到最长公共前缀来判断
然后对于每一个起始位置的答案中选一个字典序最小的

样例输入

4 2
baca

样例输出

ac

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int base= 13331;
const int N=1e6+10;

typedef unsigned ull;

int n,k,now[N];
char s[N];
ull ha[N],ba[N];

ull get(int l,int r) {
    ll ans=(ha[r]-ha[l-1]*ba[r-l+1]);
    return ans;
}

int check(int x,int y){
    int ans=0;
    int l=1,r=k;
    while(r>=l){
        int mid=l+r>>1;
        if(get(x,x+mid-1)==get(y,y+mid-1)){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return s[x+ans]<s[y+ans];
}


int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>k;
    scanf("%s",s+1);
    for(int i=n+1;i<=n*2;i++) s[i]=s[i-n];
    ba[0]=1;
    for(int i=1;i<=n*2;i++){
        ba[i]=(ba[i-1]*base);
        ha[i]=(ha[i-1]*base)+s[i];
    }
    for(int i=1;i<=n;i++){
        if(!now[i%k]) now[i%k]=i;
        else if(check(now[i%k],i)) now[i%k]=i;
    }
    int ans=now[0];
    for(int i=1;i<k;i++) if(check(now[i],ans)) ans=now[i];
    for(int i=ans;i<=ans+k-1;i++) cout<<s[i]; 



    return 0;
}