作者：hfdljflkd_863 | 来源：互联网 | 2024-12-19 12:49
引言
每当夜幕降临，我们仰望星空，心中总有许多未解之谜。今天，我们将探讨一个编程领域的难题——如何找到特定条件下的Lyndon串。这不仅是一场技术的较量，更是一次思维的碰撞。
Lyndon串简介
Lyndon串是一种特殊的字符串，其定义为：一个字符串是Lyndon串当且仅当它是该字符串的所有循环移位中字典序最小的。此外，Lyndon串不能是任何非平凡的循环串（即不能通过自身的一部分重复得到）。
问题描述
给定正整数n和字符串p，以及正整数k，我们需要找到长度不超过n且字典序大于等于p的所有Lyndon串中，字典序第k小的那个串。这个问题看似简单，实则充满挑战，尤其是当贪心策略失效时，更需要我们深入思考。
解决方案
解决这一问题的核心在于动态规划与深度优先搜索的结合。首先，我们需要计算以p开头的Lyndon串的数量x。根据x与k的关系，我们可以逐步缩小搜索范围：
- 如果x >= k，说明p是答案的前缀，但不一定就是答案。此时，我们可以将k减1，并在p后添加一个'a'继续搜索。
- 如果x
为了确保每个合法串都被恰好计算一次，我们引入了循环节的概念。对于一个合法串，若p在其内部出现了c次，则该串有c种不同的循环表示方式，每种表示方式都应为答案贡献1/c的权重。
动态规划的具体实现
我们使用一个三维数组dp[i][j][c]来表示从当前位置开始，尝试匹配p的第j个字符，已匹配c次p的方案数。通过递推公式，我们可以逐步构建出最终的解。
在具体实现中，我们还需要处理一些特殊情况，如字符串的边界条件和循环节的计算。这些细节的处理对于算法的正确性和效率至关重要。
代码实现
点击查看代码
#include
using namespace std;
typedef long long ll;
const int maxn = 53;
const int mod = 998244353;
const ll inf = 4e18;
int n, m, nxt[maxn];
ll f[maxn][maxn][maxn], g[maxn], K;
char s[maxn];
#define gcd __gcd
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch <'0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x <<1) + (x <<3) + (ch^48);
ch = getchar();
}
return x * f;
}
inline bool inc() {for( ; m&&s[m]=='z'; s[m--]=0); return m?s[m]++,1:0;}
inline void add(ll &x, ll y) {x = min(inf, x+y);}
inline ll mul(ll x, ll y) {return 1.0*x*y>2*inf?inf:min(inf, x*y);}
inline bool chk()
{
for(int i=2; i<=m; i++)
{
if(strcmp(s+1, s+i)>0) return 0;
}
return 1;
}
inline bool chk2(int j=1)
{
for(int i=2; i<=m; i++)
{
if(s[i] if(s[i] == s[j]) j++;
else j = 1;
}
return 1;
}
ll calc()
{
if(!chk2()) return 0;
for(int i=2,j=0; i<=m; i++)
{
while(j && s[j+1] != s[i]) j = nxt[j];
if(s[j+1] == s[i]) j++;
nxt[i] = j;
}
memset(f, 0, sizeof(f));
f[0][nxt[m]+1][0] = 1;
for(int i=0; i {
if(f[i][j][k])
{
add(f[i+1][j==m?nxt[m]+1:j+1][k+(j==m)], f[i][j][k]);
add(f[i+1][1][k], mul(f[i][j][k], 'z'-s[j]));
}
}
memset(g, 0, sizeof(g));
for(int i=1; i<=n; i++) for(int k=1; k<=i; k++)
{
add(g[i], mul(f[i-1][m][k-1]/(k/gcd(i,k)), i/gcd(i,k)));
}
for(int i=1; i<=n; i++) for(int j=i+i; j<=n; j+=i) if(g[j] != inf) g[j] -= g[i];
for(int i=m; i<=n; i++) if(g[i] == inf) return inf;
ll x = 0; for(int i=m; i<=n; i++) add(x, g[i]/i);
return x;
}
int main()
{
scanf("%d%lld%s", &n, &K, s+1);
m = strlen(s+1);
while(1)
{
ll x = calc();
if(K > x)
{
K -= x;
if(!inc()) puts("-1"), exit(0);
}
else
{
if(chk() && !--K) puts(s+1), exit(0);
s[++m] = 'a';
}
}
return 0;
}
在这个过程中，我们不仅解决了问题，也深化了对Lyndon串的理解。希望这篇文章能为你带来启发，激发你对算法世界的无限探索。
京公网安备 11010802041100号