[XSY] 字符串题（字符串，构造）

科技前沿 • 2025-03-16 09:13 • 阅读 49

大家好，我是讯享网，很高兴认识大家。

字符串题

考虑找到一种方法，能够对一个 lyndon 串 A ，直接求出 A 的下一个 lyndon 串。
考虑不断复制 A ，得 AAA…A
因为 lyndon 串是自身循环移位得到的串中字典序严格最小的，所以 AAA…A 非lyndon 串。
考虑微调：将 AAA…A 的末尾稍变大一些。具体方法如下：
1.若 AAA…A 的最后一位不为 ‘a’+m-1，让 AAA…A 的最后一个字符变为这个字符在字符集中的后继（如a变成b，b变成c）
2.若 AAA…A 的最后一位为 ‘a’+m-1，删去最后一位，一直删到最后一位不为 ′a′+m−1 为止，然后按1.的情况处理
（ps.其实就是找字典序比A大一的字符串A’，这样得到的串 AA…AA’ 字典序刚好比 AAA…A 大一）
可以证明 AA…AA’ 为 lyndon 串：

若循环移位后的串不以A开头：
设 $A=a_1a_2⋯a_{|A|}$ 。
由于 A 为 lyndon 串，所以对 $\forall 1 < i \leq ∣ A ∣$ ，有 $a_ia_{i+1}⋯a_{|A|}a_1a_2...a_{i-1}>a_1a_2⋯a_{|A|}$ 。所以得到的串字典序必大于 AA…AA’

讯享网

考虑怎么让 AA…AA’ 与 A 之间无其它 lyndon 串：
设 T 为 A 与 AA…AA’ 之间的一个 lyndon 串。因为 A<T<AA…AA’，所以有T=AA…AT’，其中T’ 的前 |A| 位不等于 A。

也就是说我们必须令 T中A循环部分的长度 > AA…AA’ 中A循环部分的长度的T 不符合条件，即|T|>n
那么 AA…AA’ 必须尽可能地长，我们考虑不断复制 A，然后取 AAA… 的前n位，记为 S，再找到字典序比 S 大一的字符串即可（如上文所述）。
可以证明这样得到的串是符合条件的
证明

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Que{ 
    int x,id; }que[]; int n,m,q,len; char ans[][31],ch[31]; bool cmp(Que a,Que b){ 
    return a.x<b.x; } int main(){ 
    scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=q;i++){ 
    scanf("%d",&que[i].x); que[i].id=i; } sort(que+1,que+q+1,cmp); ch[len=1]='a'; int p=1; for(int i=1;i<=q;i++){ 
    while(p<que[i].x){ 
    for(int j=len+1;j<=n;j++) ch[j]=ch[j-len]; len=n; while(ch[len]=='a'+m-1) ch[len--]=0; ch[len]++; p++; } for(int j=1;j<=len;j++) ans[que[i].id][j]=ch[j]; } for(int i=1;i<=q;i++){ 
    for(int j=1;ans[i][j];j++) putchar(ans[i][j]); puts(""); } return 0; }

讯享网

[XSY] 字符串题（字符串，构造）

相关推荐