#P10581. [蓝桥杯 2024 国 A] 重复的串

    ID: 12066 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2024矩阵加速KMP 算法蓝桥杯国赛

[蓝桥杯 2024 国 A] 重复的串

题目描述

给定一个仅含小写字母的字符串 SS,问有多少个长度为 nn 的仅含小写字母的字符串中恰好出现了两次 SS。答案对 998 244 353998\ 244\ 353 取模。

输入格式

输入一行包含一个字符串 SS 和一个整数 nn,用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

aba 6
53
aba 10
77907666

提示

对于 40%40\% 的评测用例,n20n \le 20S6|S| \le 6
另有 10%10\% 的评测用例,n500n\le 500S2|S| \le 2
对于 70%70\% 的评测用例,n105n\le 10^5
对于所有评测用例,1n1091\le n\le 10^91S301 \le |S| \le 30