#1840. [语言月赛 202505] 通配回文

[语言月赛 202505] 通配回文

题目描述

给定字符串 SS,SiS_i 表示第 ii 个字符,从 1 开始计算。例如,S=abcdS=\texttt{abcd},则 S2=bS_2=\texttt{b}。

字符串 SS 的子串是 SS 中下标连续的一部分。例如 abc\texttt{abc} 是 abcd\texttt{abcd} 的子串,而 acd\texttt{acd} 不是

字符串 tt 是通配回文串,当且仅当 tt 满足下面的条件:

  • 对于所有的 1≤i≤∣t∣1 \le i \le |t|,tit_i 和 t∣t∣−i+1t_{|t|-i+1} 匹配
  • ∣t∣|t| 表示字符串 tt 的长度
  • tit_i 和 t∣t∣−i+1t_{|t|-i+1} 匹配,是指字符 ti,t∣t∣−i+1t_i,t_{|t|-i+1} 满足下列条件中的至少一个:
    • ti=t∣t∣−i+1t_i = t_{|t|-i+1}
    • tit_i 和 t∣t∣−i+1t_{|t|-i+1} 中有一个为通配符 ?

请问字符串 SS 中有多少子串是通配回文串?

输入格式

每个测试点中包含多组测试数据。

第一行为一个整数 TT,表示测试数据的组数。

对于每组测试数据,输入一行一个字符串 SS。

输出格式

对于每组测试数据,输出一行一个整数,表示 SS 中子串是通配回文串的个数。

样例

2
tt
a?ab
3
8

题目来源:洛谷 B4331