双旋转字符串
测试数据来自 system/1960
描述
给定两个字符串集合\(\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
- 1892
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者