P6216 Palindrome Matching

For a pair of strings $(s_1, s_2)$, for every substring $[l, r]$ of $s_1$ with odd length, if $[l, r]$ is a palindrome, then the “score” of $s_1$ increases by the number of occurrences of $s_2$ inside $[l, r]$. Now you are given a pair $(s_1, s_2)$. Please compute the “score” of $s_1$. Output the answer modulo $2 ^ {32}$.

The first line contains two integers $n, m$, representing the lengths of $s_1$ and $s_2$. The second line contains two strings $s_1, s_2$.

Output one integer on a single line, representing the score of $s_1$.

**Sample Explanation** For sample 1: $s_2$ appears once in the substring $[1, 5]$, and once in the substring $[2, 4]$. $s_2$ appears once in the substring $[7, 9]$, and once in the substring $[6, 10]$. -------------------------------------- **Constraints** **This problem uses bundled testdata.** - For $100\%$ of the testdata: $1 \le n, m \le 3 \times 10 ^ 6$, and all characters in the strings are lowercase letters. - **Detailed constraints:** | Subtask ID | $n, m \le$ | Points | | :--------: | :---------------: | :----: | | $1$ | $100$ | $15$ | | $2$ | $10 ^ 3$ | $15$ | | $3$ | $5 \times 10 ^ 3$ | $20$ | | $4$ | $4 \times 10 ^ 5$ | $30$ | | $5$ | $3 \times 10 ^ 6$ | $20$ | Translated by ChatGPT 5