Codeforces 710F 字典树+后缀数组构成支持修改的AC自动机

http://codeforces.com/contest/710/problem/F

String Set Queries

time limit per test

3 seconds

memory limit per test

768 megabytes

You should process m queries over a set D of strings. Each query is one of three kinds:

  1. Add a string s to the set D. It is guaranteed that the string s was not added before.
  2. Delete a string s from the set D. It is guaranteed that the string s is in the set D.
  3. For the given string s find the number of occurrences of the strings from the set D. If some string p from D has several occurrences in s you should count all of them.

Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query of the third type. Use functions fflush in C++ and BufferedWriter.flush in Java languages after each writing in your program.

Input

The first line contains integer m (1 ≤ m ≤ 3·105) — the number of queries.

Each of the next m lines contains integer t (1 ≤ t ≤ 3) and nonempty string s— the kind of the query and the string to process. All strings consist of only lowercase English letters.

The sum of lengths of all strings in the input will not exceed 3·105.

Output

For each query of the third kind print the only integer c— the desired number of occurrences in the string s.

Examples
Input

Output

Input

Output

题意:

有一个字符串的集合D,和Q次操作。每次操作可能向D集合插入一个字符串,或者在D集合中删除一个字符串,或者询问在集合D中的所有字符串,在询问串中出现了多少次。强制在线。

题解:

由于存在删除和插入,所以不能直接用AC自动机解决这个问题。考虑插入和删除用字典树来维护,对于每一次询问,构建询问串的后缀数组,按照后缀字典序,将每一个后缀在字典树中进行查询,统计答案即可。当询问完第i个后缀后,直接在字典树上暴力退回到后一个串的height位置即可。下一个串直接从这个位置开始查询字典树。

 

HDU 5853 Jong Hyok and String 后缀数组 二分 RMQ

http://acm.split.hdu.edu.cn/showproblem.php?pid=5853

Jong Hyok and String

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

Input

First line contains T, a number of test cases.

For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)

1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
ni=1|Pi|≤100000
File size is less than 3.5 megabytes.

Output

For each test case, first line contains a line “Case #x:”, x is the number of the case.

For each question, you should print one integer in one line.

Sample Input

1
2 2
aba
ab
a
ab

Sample Output

Case #1:
1
2

Hint

strange set(“a”) ={(1, 1), (1, 3), (2, 1)}.
strange set(“ab”) ={(1, 2), (2, 2)}.
strange set(“b”) ={(1, 2), (2, 2)}.

Author

金策工业综合大学(DPRK)

Source

2016 Multi-University Training Contest 9

题意

给定n个字符串Pi,(1<=n<=105,Pi的总长度小于105)。然后是m次询问,每次询问给出一个字符串Qi,Qi的长度小于105,定义集合set(s)={(i,j)|字符串s出现在Pi中,且最后一个字符的位置为j}。询问有多少个不同的字符串t,使得set(t)和set(Qi)相同。

思路

由于题叙的位置为出现字符串的最后一个字符的位置,可以考虑将所有字符串倒序,那么这个位置就变成的第一次字符的位置。(后面说的串都是反转之后的)。考虑t=Qi的情况,这个t是显然可以的。若让t删除几个末尾的字符,set(t)只会在原有的基础上,增加元素,或者是不增加。若让t在末尾增加几个字符,set(t)也只会在原有的基础上,减少元素,或者不减少。这里增加长度的时候,只考虑在和某个Pi的某个位置匹配的时候,增加后面的字符。那么增加后使set(t)不变的最长长度,删减后,使set(t)不变的最短长度,这两个的差值+1就是答案。

将所有的Pi串连到一起,用不同的特殊符合隔开,这个用#表示,构成一个串s。注意,每个#的值都是不同的。构建关于s的后缀数组。每次询问一个串Qi的时候。二分查找Qi第一次出现在后缀数组中的位置low和最后一次出现的位置high。当然,如果没有出现Qi串,那么答案一定就是0了。考虑最小长度,可以发现,就是max(height[low],height[high+1])+1,如果删减到小于这个长度,会使得set(t)的元素数目变多。那么最大长度,则使min(height[low+1……height]),这个用rmq维护即可。但是如果low==high的时候,最小长度还是可以按照上述方法求的,但是最大长度则是这个起始位置到后面离它最近一个#的距离。