P3318 [SDOI2015] Double Rotation Strings

Given two sets of strings $\mathcal{S}$ and $\mathcal{T}$. All strings in $\mathcal{S}$ have length exactly $N$, and all strings in $\mathcal{T}$ have length exactly $M$. Moreover, $N + M$ is even. If we denote all strings in $\mathcal{S}$ by $S_1, S_2, \dots, S_{Total_S}$, and all strings in $\mathcal{T}$ by $T_1, T_2, \dots, T_{Total_T}$, we want to know how many pairs $\langle i, j \rangle$ satisfy that the concatenation $S_i + T_j$ has the double rotation property. An even-length string $W$ can be written as the concatenation of two strings of equal length, i.e., $W = U + V$. If $V$ can be obtained from $U$ by a rotation (cyclic shift), then $W$ is said to have the double rotation property. For example, the string `vijos` can be rotated to `ijosv`, `josvi`, `osvij`, or `svijo`. Thus, `vijosjosvi` has the double rotation property.

The first line contains four positive integers $Total_S, Total_T, N, M$, denoting respectively the size of set $\mathcal{S}$, the size of set $\mathcal{T}$, the length of strings in $\mathcal{S}$, and the length of strings in $\mathcal{T}$. The next $Total_S$ lines each contain a string $S_i$, $1 \le i \le Total_S$. Each string has length exactly $N$, and consists only of the 26 lowercase letters. The next $Total_T$ lines each contain a string $T_i$, $1 \le i \le Total_T$. Each string has length exactly $M$, and consists only of the 26 lowercase letters.

Output a single integer, the number of pairs $\langle i, j \rangle$ that satisfy the requirement.

For $10\%$ of the testdata, $1 \leq N \leq 100$, $1 \leq M \leq 100$, $1 \leq Total_S \leq 100$, $1 \leq Total_T \leq 100$. For $30\%$ of the testdata, $1 \leq N \leq 500$, $1 \leq M \leq 500$, $1 \leq Total_S \leq 500$, $1 \leq Total_T \leq 500$. For $60\%$ of the testdata, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^5$. For $100\%$ of the testdata, $2 \le N \times Total_S + M \times Total_T \le 4 \times 10^6$. Translated by ChatGPT 5