부분 문자열

시간 제한2초메모리 제한512 MB

요약

문자열 위의 구간 [l, r]이 한 번에 한 끝점만 움직이며 m번 변할 때, 지금까지 등장한 서로 다른 부분문자열의 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열, 정렬, 문자열 매칭, 구현
정답자: 아직 제출이 없습니다

문제

길이 $n$ 인 문자열 $s = s_1, s_2, \ldots, s_n$ 과 $m$ 개의 쿼리가 주어진다. 각 쿼리 $q_k$ ( $1 \le k \le m$ )는 "L++", "L--", "R++", "R--" 중 하나이며, $k$ 번째 쿼리 $q_k$ 에 대해 $l[k]$ 와 $r[k]$ 를 다음과 같이 정의한다.

L++: $l[k] = l[k-1] + 1$ , $r[k] = r[k-1]$
L--: $l[k] = l[k-1] - 1$ , $r[k] = r[k-1]$
R++: $l[k] = l[k-1]$ , $r[k] = r[k-1] + 1$
R--: $l[k] = l[k-1]$ , $r[k] = r[k-1] - 1$

단, $l[0] = r[0] = 1$ 이다.

이때 $m$ 개의 부분 문자열 $s_{l[k]}, s_{l[k]+1}, \ldots, s_{r[k]-1}, s_{r[k]}$ ( $1 \le k \le m$ ) 가운데 서로 다른 문자열이 몇 개인지 구하라.

입력

입력은 다음 형식으로 주어진다.

n m
s
q1
q2
…
qm

출력

문제의 답을 한 줄에 출력한다.

제한

문자열 $s$ 는 소문자 알파벳으로 이루어진다.
$1 \le n \le 3 \times 10^5$
$1 \le m \le 3 \times 10^5$
$q_k$ ( $1 \le k \le m$ )는 "L++", "L--", "R++", "R--" 중 하나이다.
$1 \le l[k] \le r[k] \le n$ ( $1 \le k \le m$ )

예제3

예제 1
입력
```
5 4
abcde
R++
R++
L++
L--
```
예상 출력
```
3
```
예제 2
입력
```
4 6
abab
R++
L++
R++
L++
R++
L++
```
예상 출력
```
4
```

예제 3

입력

10 13
aacacbabac
R++
R++
L++
R++
R++
L++
L++
R++
R++
L--
L--
R--
R--

예상 출력