茴芠是個回文愛好者,常常會收集一些字串,裡面有著各式各樣的回文。
有一天他在大掃除,想把收藏的字串整理一下,看看這些收藏的字串中有多少回文
但由於字串實在太長了,茴芠一個人數不完而現在茴芠想請你幫忙,
茴芠給你一個字串 $s$,每次問你裡面有幾個長度為 $k$ 的回文
以便茴芠統計他所蒐集的回文數量,讓他計算完之後好跟朋友炫耀
回文,亦稱迴文、回環,是正讀反讀都能讀通的句子
多筆測資
第一行有一個正整數 $T(T\le 2 \cdot 10^4)$,代表總共 $T$ 筆測資
每筆測資共 $4$ 行
第一行有一個正整數 $n(1\le n\le 2 \cdot 10^5)$ ,代表字串 $s$ 的長度
第二行有一個長度為 $n$ 的字串 $s$ ,保證裡面只有小寫字母
第三行有一個正整數 $q(1\le q \le 2 \cdot 10^5)$,代表詢問數
第四行有 $q$ 個正整數 $k_i (1 \le k_i \le n)$ 代表詢問長度為 $k_i$ 的回文有幾個
* 保證所有 $n, q$ 加起來分別不超過 $2 \cdot 10^5$
共 $T$ 行,
每行分別依序輸出每筆測資的答案
2 2 bb 2 1 2 5 ababa 3 1 3 5
2 1 5 3 1
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |