###### 编程介的小学生

2018-12-14 12:47 阅读 401

# 求问一个字符串的匹配算法的难题，要规定使用c语言才能实现？

Problem Description
Using data compression technique, the long string `ruiruiruiruiruirui" can be compressed into`(ruirui)3" or `(rui)6". To simplify the technique, multiple compressions are not allowed. For example, we don't allow to compress the string`princessruiruiprincessruirui" into ``(princess(rui)2)2".

Now for given string S and k patterns using the mentioned technique, we want to distinguish each pattern which is a prefix of S. We emphasize that a pattern as a string can be cyclic shifted. For example, a pattern `abcd" can be shifted into`bcda", `cdab" or`dabc".

Input
The first line contains an integer t (1≤t≤13) which is the number of test cases.

For each test case, the first line is the string S. The second line contains the integer k(1≤k≤10) and following k lines list the patterns, labelled from 1 to k.
The string S and all patterns only contain lower-case letters, numbers and parentheses. Numbers of replication are positive integers no more than 2×108. The length of S is no more than 11000. The length of each pattern is no more than 11000 as well. We guarantee that the actual length of each T (the length of the original pattern without compression) would be smaller than the actual length of S (the length of original S without compression). The length of each substring given in parentheses is no more than 10.

Output
For each test case, output the sum of labels' squares for patterns as the prefix of S.

Sample Input
3
z(rz)3r(rui)2cumt
5
(zr)4
zrzrrui
zr(zr)2z(r)2u
(rz)3
(zr)2z(r)2zr
(ab)2aab(aba)3(ba)2(zhang)940712
4
(babaa)2(baa)2
(aabab)2
(ab)3
(aba)2(ab)3a(ab)2(a)2b
(a)100b(a)100c(a)100d
1
(a)100d(a)100c(a)100b

Sample Output
Case #1: 51
Case #2: 21
Case #3: 0

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享