글자 하나를 추가해도 될까?

시간 제한2.5초메모리 제한1024 MB

요약

문자열 끝에 문자를 추가하거나 마지막 문자를 삭제할 때마다, 두 번 이상 나타나는 서로 다른 부분 문자열의 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 문자열, 문자열 매칭, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 문자열 S가 있습니다. S에 대해 다음 두 종류의 갱신을 총 $Q$ 번 차례대로 수행합니다.

주어진 문자를 S의 끝에 붙인다.
S의 마지막 문자를 삭제한다.

처음 상태와 각 갱신을 마친 뒤마다, S의 부분 문자열로 두 번 이상 나타나는 서로 다른 문자열의 개수를 구하세요.

예를 들어 처음 S가 ABABC이면 A, B, AB가 각각 S의 부분 문자열로 두 번씩 나타나므로 답은 3입니다. 문자 C를 붙이면 S는 ABABCC가 되고, 이제 C도 두 번 나타나므로 답은 4입니다. C를 한 번 더 붙이면 S는 ABABCCC가 되고, CC도 두 번 나타나므로 답은 5입니다. 여기서 삭제를 하면 S는 ABABCC가 되고 답은 다시 4가 됩니다.

입력

첫 줄에 길이가 $N$ 인 문자열 S가 주어집니다. S의 초기 값입니다. S의 각 문자는 대문자 알파벳입니다.

둘째 줄에 길이가 $Q$ 인 문자열 U가 주어집니다. U는 갱신 내용입니다. U의 각 문자가 대문자이면 그 문자를 끝에 붙이고, 하이픈 -이면 마지막 문자를 삭제합니다. 갱신은 U에 나타난 순서대로 적용합니다. 빈 문자열에 삭제 연산이 적용되는 경우는 없습니다.

제한: $1 \le N \le 10^5$ , $1 \le Q \le 10^5$ .

출력

$Q + 1$ 개의 줄을 출력합니다. 첫 줄은 S의 초기 값에 대한 답입니다. $i + 1$ 번째 줄은 처음 $i$ 번의 갱신을 적용한 뒤의 답입니다( $i = 1, 2, \ldots, Q$ ).

예제3

예제 1
입력
```
ABABC
CC-
```
예상 출력
```
3
4
5
4
```
예제 2
입력
```
ABAB
A--CC
```
예상 출력
```
3
5
3
1
1
2
```
예제 3
입력
```
HAVE
FUN
```
예상 출력
```
0
0
0
0
```