#基数排序#CF1654F Minimal String Xoration

题目传送门

分析

有没有一种办法可以将每个 \(j\) 的比较过程同时进行，

可以发现其实这个过程很像后缀排序，实际上只是加号变成了异或，

从低位到高位重新将字符串排名，用同样的方法做到 \(O(2^nn)\)

代码

#include 
using namespace std;
const int N=300011; string S;
int n,two[N],rk[N],tp[N],Rk[N],M,c[N];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>S,two[0]=1;
	for (int i=1;i<=n;++i) two[i]=two[i-1]<<1;
	for (int i=0;i
String-SA、SAM、Lyndon只是前置-位运算、倍增、高精

相关

标签