OpenJudge

5:Hrinity

总时间限制:
3000ms
内存限制:
655360kB
描述

In the Christian religion, the Trinityis the union of the Father, the Son, and the Holy Spirit in one God. Recently in a far-far-away country, a new word "Hrinity" was created and becam every popular. "Hrinity" means "The son is the father, and the father is the son."  But the word "Hrinity" has nothing to do with God or any religion. It's about awriter and his son.

When the son was in high school, he failed all exams of all courses. As a none famous writer, the son's worrying fathercarried out a bold plan: he wrote a long novel and declared that it's his 16year old son's work. An idiot kid can write a long novel? That made a press interestedand the press published the novel. Since then, the son got famous and rich, andhis father has been keep writing novels and articles on his son's name.

But the father doesn't trust his sonbecause his son is a punk. Afraid of being treated badly by his son when becoming old, the father embedded "text finger prints" in all the novels and articles. If the son treats him badly, the father will stand out and declare that his son is a fake writer. The father can point out the "textfinger prints" in those works to prove that he actually is the author. A text finger print is a delicate sentencewhich if you adddeleteor change the punctuations in it, it's meaning will become totally different. In all his works, the father write many text finger prints whose meaning can be changed into something like "my father wrote this article""I am a fake writer", etc. In case of forgetting where the finger prints are,the father needs a computer program to find out how many finger prints arethere in a given article. He offers $20,000,000 to buy the program. Do you want this money?

To simplify the problem, we assume that the articles are all written in capital English letters and without blanks.

输入
There are multiple test cases. The first line in the input is an integer T ( T<= 15) indicating the number of test cases.
For each test case:
The first line is a integer n( 0 < n <= 2500) indicating the number of text finger prints.
Then n lines follows, each represents a text finger print. It’s guaranteed that these n strings are all different. A finger print at least consists of one letter.
The last line of a test case is the article.
The text finger prints and the article may be described in a compressed format. A compressed string consists of capital letters and “compressors”. A “compressor” is in the following format:

[qx]

q is a number( 0 < q <= 5,000,000)and x is a capital letter. It means q consecutive letter xs in the original uncompressed string. For example, [6K] means ‘KKKKKK’ in the original string. So, if a compressed string is like:

AB[2D]E[7K]G

It actually is ABDDEKKKKKKKG after decompressed to original format.
The length of the article is at least 1 and at most 5,100,000, no matter in the compressed format or after it is decompressed to original format. The length of a text finger print is no more than 1,100, no matter compressed or original.
输出
For each test case, print an integer K in a line meaning that the article includes K text finger prints. PLEASE NOTE: If finger print s1 is a sub string of finger print s2 and s2 is included in the article, then s1 doesn't count (s1 can be regarded as doesn't exists). Multiple appearances of a finger print in the article are just counted as one.
样例输入
4
2
AB
DCB
DACB
3
A
AB
ABC
DABC
2
[2A]
[3A]B
[5A]B[4A]B
3
AB
CD
EF
ABCDEF
样例输出
0
1
1
3
全局题号
5140
添加于
2016-07-28
提交次数
0
尝试人数
0
通过人数
0