|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|0.5 초||256 MB||19||13||11||64.706%|
K. has stumbled upon a weird game while playing on his computer. The game consists of an initial string S of length N (1 ≤ N ≤ 1000) and an empty set T. The following events might occur during the game:
Because K. wants to go visit a famous castle near his hometown, you must help him deal with the game as quickly as possible.
The first line of the input contains two integers: N, the length of the initial string S and E, the number of events (E ≤ 1200000).
The second line describes the string S; the string consists only of lowercase Roman alphabet (a-z).
The following E lines describe the events. Each of these lines contains an integer p, describing the event type.
If p is 1, then it is followed by a character (a-z), which will be added at the end of S.
If p is 2, then the string S is added in T.
If p is 3, then you must respond to the query “How many strings in T are suffixes of the current S?”
The output should consist of a line containing an integer for each type 3 event in the input, which represents the answer to the query.
Note: T is a set, so it doesn't contain duplicates.
Note: Large input: for C scanf and printf recommended; for C++, add “
cin.tie(NULL);” before reading; for Java use BufferedReader and BufferedWriter.
1 11 a 2 1 b 1 a 2 2 1 c 1 a 3 1 b 1 a 3