当前位置:首页 > 字符串 > 正文
洛谷P7114字符串匹配(NOIP2020)
155+

题目大意:一个字符串,划分成ABC、ABABC、ABABABC……要求字符串A中出现奇数次数的字符种数不超过字符串C,有多少中划分方案?

题目描述

小 C 学习完了字符串匹配的相关内容,现在他正在做一道习题。

对于一个字符串 ,题目要求他找到 的所有具有下列形式的拆分方案数:

,其中 均是非空字符串,且 中出现奇数次的字符数量不超过 中出现奇数次的字符数量。

更具体地,我们可以定义 表示两个字符串 相连接,例如 ,则

并递归地定义 且为正整数)。例如 ,则

则小 C 的习题是求 的方案数,其中 表示字符串 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 中有至少一个字符串不同。

小 C 并不会做这道题,只好向你求助,请你帮帮他。

输入格式

本题有多组数据,输入文件第一行一个正整数 表示数据组数。

每组数据仅一行一个字符串 ,意义见题目描述。 仅由英文小写字母构成。

输出格式

对于每组数据输出一行一个整数表示答案。

输入输出样例

输入 #1
3
nnrnnr
zzzaab
mmlmmlo
输出 #1
8
9
16
输入 #2
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab
输出 #2
156
138
138
147
194
输入 #3
见附件中的 string/string3.in
输出 #3
见附件中的 string/string3.ans
输入 #4
见附件中的 string/string4.in
输出 #4
见附件中的 string/string4.ans

说明/提示

【样例 #1 解释】

对于第一组数据,所有的方案为

【数据范围】

测试点编号 特殊性质
中只包含一种字符
中只包含两种字符

对于所有测试点,保证

解题思路

暴力:枚举A、B,确定C,判断是否满足条件,满足就累加1,至少可得32分;预处理前缀、后缀奇数种类数量,可得48。

判断AB翻倍,可以使用strncmp、哈希、KMP判循环节等。

程序实现

暴力枚举A、B,翻倍确定C,可得48:

枚举BC,最后枚举A,显然可以预处理前缀和:预处理出前i个位置,有多少个奇数种类不超过j的前缀(子串)。

使用KMP算法判循环节,总体时间复杂度是$O(T*n*log_2n)$,部分OJ满分。

程序中,c[j]记录奇数种类不超过j个的前缀数量(结尾数量),只增不减,因为多一个字符只会多一个前缀。多了的这个前缀,如果是奇数种类是5,那么对于出现5、6、7、……、26次的C串,都可以增加一个匹配。

用哈希判断循环节,洛谷满分,其他OJ容易超时92分。

About

坚决不Copy代码!

本文标签:,,,,,,,,,,

洛谷P7114字符串匹配(NOIP2020):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter