/ Vijos / 题库 /

双旋转字符串

双旋转字符串

描述

给定两个字符串集合\(\mathcal{S}\)和$\(\mathcal{T}\)。其中\(\mathcal{S}\)中的所有字符串长度都恰好为N,而\(\mathcal{T}\)中所有字符串长度都恰好为M,且N+M恰好为偶数。

如果记\(\mathcal{S}\)中字符串全体为\(S_1,S_2,\cdots,S_{Total_S}\),而\(\mathcal{T}\)中字符串全体为\(T_1,T_2,\cdots,T_{Total_T}\)。现在希望知道有多少对\(\langle i,j\rangle\),满足将\(S_i\)和\(T_j\)拼接后得到的字符串\(S_i+T_j\)满足双旋转性。

一个长度为偶数字符串\(W\)可以表示成两段长度相同的字符串的拼接,即W=U+V。如果V可以通过U旋转得到,则称W是满足双旋转性的。比如说字符串U=“vijos”,可以通过旋转得到“ijosv”,“josvi”,“osvij”或“svijo”。那么“vijosjosvi”就是满足双旋转性的字符串。

格式

输入格式

第一行输入四个正整数,分别为\(Total_S\),\(Total_T\),N和M,依次表示集合\(\mathcal{S}\)的大小,集合\(\mathcal{T}\)的大小,集合\(\mathcal{S}\)中字符串的长度和集合\(\mathcal{T}\)中字符串的长度。

之后\(Total_S\)行,依次给出\(\mathcal{S}\)中所有的字符串S_i,\(1\le i\le Total_S\)。保证每一个字符串长度都恰为N,且字符串只由26个小写字母组成。

之后\(Total_T\)行,依次给出\(\mathcal{T}\)中所有的字符串\(T_i\),\(1\le i\le Total_T\)。保证每一个字符串长度都恰为M,且字符串只由26个小写字母组成。

输出格式

输出一个整数,表示满足要求的数字对\(\langle i,j\rangle\)有多少个。

样例1

样例输入1

4 4 7 3
vijosvi
josvivi
vijosos
ijosvsv
jos
vij
ijo
jos

样例输出1

6

限制

对于10%的数据,\(1\le N\le 100,~1\le M\le 100,~1\le Total_S\le 100,~1\le Total_T\le 100\)。
对于30%的数据,\(1\le N\le 500,~1\le M\le 500,~1\le Total_S\le 500,~1\le Total_T\le 500\)。
对于60%的数据,\(2\le N\times Total_S + M\times Total_T \le 4\times 10^5\)。
对于100%的数据,\(2\le N\times Total_S + M\times Total_T \le 4\times 10^6\)。

来源

SDOI2015 round2 day1

信息

ID
1960
难度
7
分类
(无)
标签
递交数
272
已通过
42
通过率
15%
上传者