#2787. Spoj 11482. Count on a trie

题目描述

Maintain two sets of strings S and T.Initially,each set contains an empty string with id 1.
Your program are to perform the following four operations:

1.Add a char c to the end of an existed string Si in S,then insert the new string into S.Since there has been n strings in S already,the new string will hold the id n+1.
2.Add a char c to the beginning or to the end of an existed string Ti in T,then insert the new string into T.
3.Choose two existed strings Ti and Tj from T,next combine them into a new one TiTj,then insert the new string into T.
4.Print the time that an existed string Ti in T appears in an string Si in S.Your program should print 0 if Ti is an empty string.

维护两个字符串集合S,T，一开始S和T都只有一个空串,编号都为1,要求支持操作:
1.在S的某一个串Si后添加一个字符c，加入S
2.在T的某一个串Ti的前面或后面添加一个字符c，加入T
3.将T的两个串Ti,Tj首尾相接形成一个新串TiTj，加入T
4.询问T中的某个串Ti在S中某个串Si中的出现次数.（如果Ti是空串，输出0）

输入格式

In the first line,there is an integer Q,which means the number of operations to perform.
In the next Q lines,the i-th line describes the i-th operation containing some integers.Such a line may look like this:
1 Si c
2 0 Ti c =>add c to the beginning of Ti
2 1 Ti c =>add c to the end of Ti
3 Ti Tj
4 Ti Si

Q<=300000,'a'<=c<='z'
The number of the first operation will not exceed 100000.
The number of the third operation will not exceed 30000.
The number of fourth operation will not exceed 100000.

输出格式

For each "4 Ti Si" operation,print its result;

样例

样例输入

18  

1 1 a  

1 2 a  

1 3 b  

1 2 b  

1 5 a  

1 5 b  

2 1 1 a  

3 2 2  

2 0 3 b  

2 1 2 b  

3 2 5  

3 5 2  

4 7 6  

4 5 6  

4 3 4  

4 2 4  

4 2 7  

4 2 6  

样例输出

1  

1  

1  

2  

1  

2

数据范围与提示