solution
其实本题只要解决一个问题,剩下的就是模拟了。
这个问题就是如何快速的比较两个字符串的字典序。这是一个非常经典的思路。我们对这两个字符串都哈希一遍,然后二分一下这两个字符串最长的公共前缀长度。然后比较最长公共前缀的下一位上的字符就行了。因为所有要比较的字符串都在同一个母串上。我们只要对这个母串进行一遍哈希就行了。
剩下的按照题目中讲的模拟即可。
code
/* * @Author: wxyww * @Date: 2020-04-17 19:15:03 * @Last Modified time: 2020-04-17 19:23:46 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1000010; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } char s[N]; ull hs[N],base[N],B = 28; int n,K,now[N]; ull get(int l,int r) { return hs[r] - hs[l - 1] * base[r - l + 1]; } int check(int x,int y) { int l = 1,r = K,ans = 0; while(l <= r) { 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() { n = read(),K = read(); scanf("%s",s + 1); for(int i = n + 1;i <= n + n;++i) s[i] = s[i - n]; base[0] = 1; for(int i = 1;i <= n + n;++i) { hs[i] = hs[i - 1] * B + s[i] - 'a' + 1; base[i] = base[i - 1] * B; } 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) putchar(s[i]); return 0; }