서로 다른 부분 문자열 쿼리

문자열 뒤에 문자를 붙이고 앞에서 문자를 빼는 연산을 백만 번까지 수행하면서, 매 연산 직후 서로 다른 부분 문자열의 개수를 구한다.

어려움9문자열문자열 매칭정렬트라이아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제1

문제

처음에 빈 문자열 $S$ 가 있다. 다음 두 종류의 쿼리를 차례대로 수행하는 프로그램을 작성하시오.

+ c: $S$ 의 맨 뒤에 문자 $c$ 를 추가한다. $c$ 는 알파벳 소문자이다.
-: $S$ 의 맨 앞 글자를 제거한다.

각 쿼리를 수행한 직후 $S$ 의 길이는 항상 양수이다.

쿼리를 하나 수행할 때마다 그 시점의 $S$ 에 있는 서로 다른 부분 문자열의 개수를 구해야 한다.

입력

첫째 줄에 쿼리의 개수 $Q$ 가 주어진다. ( $1 \le Q \le 1\,000\,000$ )

둘째 줄부터 $Q$ 개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

출력

각 쿼리를 수행한 직후 $S$ 의 서로 다른 부분 문자열의 개수를 구하고, 이 값을 모든 쿼리에 대해 더한 합을 $1\,000\,000\,007$ 로 나눈 나머지를 출력한다.

힌트

첫 번째 예제에서 각 쿼리 직후의 상태는 다음과 같다.

$S$ = a이다. 서로 다른 부분 문자열은 a로 1개이다.
$S$ = ab이다. 서로 다른 부분 문자열은 a, b, ab로 3개이다.
$S$ = aba이다. 서로 다른 부분 문자열은 a, b, ab, ba, aba로 5개이다.
$S$ = abaa이다. 서로 다른 부분 문자열은 a, b, ab, ba, aa, aba, baa, abaa로 8개이다.
$S$ = baa이다. 서로 다른 부분 문자열은 a, b, ba, aa, baa로 5개이다.
$S$ = aa이다. 서로 다른 부분 문자열은 a, aa로 2개이다.
$S$ = a이다. 서로 다른 부분 문자열은 a로 1개이다.
$S$ = aa이다. 서로 다른 부분 문자열은 a, aa로 2개이다.

합은 $1 + 3 + 5 + 8 + 5 + 2 + 1 + 2 = 27$ 이고, $27 \bmod 1\,000\,000\,007 = 27$ 이므로 답은 27이다.

Loading...