#1840. [语言月赛 202505] 通配回文
[语言月赛 202505] 通配回文
题目描述
给定字符串 , 表示第 个字符,从 1 开始计算。例如,,则 。
字符串 的子串是 中下标连续的一部分。例如 是 的子串,而 不是
字符串 是通配回文串,当且仅当 满足下面的条件:
- 对于所有的 , 和 匹配
- 表示字符串 的长度
- 和 匹配,是指字符 满足下列条件中的至少一个:
- 和 中有一个为通配符
?
请问字符串 中有多少子串是通配回文串?
输入格式
每个测试点中包含多组测试数据。
第一行为一个整数 ,表示测试数据的组数。
对于每组测试数据,输入一行一个字符串 。
输出格式
对于每组测试数据,输出一行一个整数,表示 中子串是通配回文串的个数。
样例
2
tt
a?ab
3
8
题目来源:洛谷 B4331