SP11482 COT4 - Count on a trie

任务：维护两个字符串序列S和T，这两个集合在开始时都只有一个编号为1的空字符串。 你的程序需要支持以下操作： 1. 在S中的一个保证存在的字符串$S_i$的末尾添加一个字符$c$,然后将新的字符串插入S。如果集合中已经有n个字符串，那么这个新的字符串编号为$n+1$ 2. 在T中一个保证存在的字符串$T_i$的头部或尾部添加一个字符$c$,再按照上述规则插入T 3. 从T中取出两个字符串$T_i$,$T_j$，将这两个字符串拼接起来（$T_i$在前），按上述规则插入T 4. 回答T中指定字符串$T_i$在S中指定字符串$S_i$的出现次数。如果$T_i$是个空串，应当输出0

第一行一个整数Q表示操作次数 接下来Q行，每行有一个操作，操作的格式如下： - $1$ $S_i$ $c$ - $2$ $0$ $T_i$ $c$ 表示在头部插入字符 - $2$ $1$ $T_i$ $c$ 表示在尾部插入字符 - $3$ $T_i$ $T_j$ - $4$ $T_i$ $S_i$ 特别规定：操作1不超过100000次，操作3不超过30000次，操作4不超过100000次。总的操作次数Q不超过300000，字符集是{'a'..'z'}

对于每个操作4，你需要输出一个整数表示答案，输出后换行