思路

把所有长为 $k$ 的串拿出来当做点，转移当做边，建图。

可以发现这是一个基环内向树森林。因为每次把众数的出现次数增加，众数当然不会改变，于是一个点的出度就是 1。

一个结论是图的大小是 $\mathcal O(n+k)$ 的。

证明分两种情况，一个是最后出现循环，另一个是最后全 a，样例里都有的。

用哈希把图建出来然后利用循环直接输出即可。

code

一开始写 map 套 map，波兰 OJ 上直接过了，洛谷 1.6s 真菜。

换了 unordered_map，能快很多。

内层用数组的话空间复杂度会多一个 $V$，但是看别人写的感觉只差一倍啊啊啊。

#include<stdio.h>
#include<unordered_map>
#include<map>
#define N 2000009
#define base 29ll
#define mod 19260817191981181ll
using namespace std;
int n,m,l,r;char s[N];unordered_map<long long,map<char,int> >mmp;
unordered_map<long long,int>cir;long long a,b,hsh[N],pw=1;
inline long long get(int i)
	{return(hsh[i]-(__int128)(hsh[i-m])*pw%mod+mod)%mod;}
main()
{
	scanf("%d%d%lld%lld%s",&n,&m,&a,&b,s+1);
	for(int i=m;i--;pw=pw*base%mod);
	for(int i=1;i<=n;++i)hsh[i]=(hsh[i-1]*base+s[i]-'a')%mod;
	for(int i=m+1;i<=n;++i)++mmp[get(i-1)][s[i]];
	for(int i=n+1;;++i)
	{
		map<char,int>&tmp=mmp[get(i-1)];
		int maxn=0;s[i]='a';
		for(map<char,int>::iterator it=tmp.begin();it!=tmp.end();++it)
			if(it->second>maxn)maxn=it->second,s[i]=it->first;
		++mmp[get(i-1)][s[i]];hsh[i]=(hsh[i-1]*base+s[i]-'a')%mod;
		if(cir.count(get(i))){l=cir[get(i)];r=i;break;}
		cir[get(i)]=i;
	}
	for(;a<=b;++a)putchar(a<=r?s[a]:s[(a-l)%(r-l)+l]);
}