对网站有效的优化软件,网站建设 不违背,如何建单页网站栏目,杭州app软件开发字符串题
考虑找到一种方法#xff0c;能够对一个 lyndon 串 A #xff0c;直接求出 A 的下一个 lyndon 串。考虑不断复制 A #xff0c;得 AAA…A因为 lyndon 串是自身循环移位得到的串中字典序严格最小的#xff0c;所以 AAA…A 非lyndon 串。考虑微调#xff1a;将 AA…字符串题
考虑找到一种方法能够对一个 lyndon 串 A 直接求出 A 的下一个 lyndon 串。考虑不断复制 A 得 AAA…A因为 lyndon 串是自身循环移位得到的串中字典序严格最小的所以 AAA…A 非lyndon 串。考虑微调将 AAA…A 的末尾稍变大一些。具体方法如下 1.若 AAA…A 的最后一位不为 ‘a’m-1让 AAA…A 的最后一个字符变为这个字符在字符集中的后继如a变成bb变成c 2.若 AAA…A 的最后一位为 ‘a’m-1删去最后一位一直删到最后一位不为 ′a′m−1 为止然后按1.的情况处理 ps.其实就是找字典序比A大一的字符串A’这样得到的串 AA…AA’ 字典序刚好比 AAA…A 大一可以证明 AA…AA’ 为 lyndon 串 若循环移位后的串以A开头 则必有A…AA’A…AAAA…AA’。 若循环移位后的串不以A开头 设 Aa1a2⋯a∣A∣Aa_1a_2⋯a_{|A|}Aa1a2⋯a∣A∣ 。 由于 A 为 lyndon 串所以对 ∀1i≤∣A∣∀1i≤|A|∀1i≤∣A∣ 有 aiai1⋯a∣A∣a1a2...ai−1a1a2⋯a∣A∣a_ia_{i1}⋯a_{|A|}a_1a_2...a_{i-1}a_1a_2⋯a_{|A|}aiai1⋯a∣A∣a1a2...ai−1a1a2⋯a∣A∣ 。所以得到的串字典序必大于 AA…AA’ 考虑怎么让 AA…AA’ 与 A 之间无其它 lyndon 串 设 T 为 A 与 AA…AA’ 之间的一个 lyndon 串。因为 ATAA…AA’所以有TAA…AT’其中T’ 的前 |A| 位不等于 A。 若 T 中A循环部分的长度 AA…AA’ 中A循环部分的长度 因为 AA…AT’AA…AA’所以 T’A 则以 T′ 开头的循环移位小于等于 T 与 T 是 lyndon 串矛盾 若 T 中A循环部分的长度 AA…AA’ 中A循环部分的长度 必有 ATAA…AA’且根据之前的结论只要令 T’AT 必为 lyndon 串 也就是说我们必须令 T中A循环部分的长度 AA…AA’ 中A循环部分的长度 的T 不符合条件即|T|n那么 AA…AA’ 必须尽可能地长我们考虑不断复制 A然后取 AAA… 的前n位记为 S再找到字典序比 S 大一的字符串即可如上文所述。可以证明这样得到的串是符合条件的 证明
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
struct Que{int x,id;
}que[200010];
int n,m,q,len;
char ans[200010][31],ch[31];
bool cmp(Que a,Que b){return a.xb.x;
}
int main(){scanf(%d%d%d,n,m,q);for(int i1;iq;i){scanf(%d,que[i].x);que[i].idi;}sort(que1,queq1,cmp);ch[len1]a;int p1;for(int i1;iq;i){while(pque[i].x){for(int jlen1;jn;j) ch[j]ch[j-len];lenn;while(ch[len]am-1) ch[len--]0;ch[len];p; }for(int j1;jlen;j) ans[que[i].id][j]ch[j];}for(int i1;iq;i){for(int j1;ans[i][j];j) putchar(ans[i][j]);puts();}return 0;
}
