總召好帥!!!
給你兩個長度皆為 $N$ 的字串 $S,T$ ,以及很多個詢問字串 $P$ ,對於每個詢問字串求有多少個配對 $(i,j)$ 滿足 $S$ 的前 $i$ 個字元和 $T$ 的第 $i+1$ 個字元以後的這兩個子字串皆不包含 $P$ ,而若把這兩個字串串接起來後會在位置 $j$ 出現 $P$ 。
正式的來說就是 $S_{1..i}, T_{i+1..N}$ 皆不包含 $P$ ,而 $S_{1..i}+T_{i+1..N}$ (字串串接)包含 $P$ 在位置 $j$ ,也就是 $(S_{1..i}+T_{i+1..N})_{j..j+|P|-1}=P$,求有多少相異的 $(i,j)$ 滿足條件。
前兩行各有一個字串 $S,T$ 為給定的兩字串。
第三行有一個正整數 $Q$ 代表詢問筆數。
接下來有 $Q$ 行每行一個詢問的字串 $P$。
輸出一共 $Q$ 行,對於每筆詢問輸出一個正整數為題目所求的答案。
IOICamp 2021 Day3 pD
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~29 | 無額外限制 | 100 |