시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 28 14 10 50.000%

문제

비어있는 문자열 S가 있다. 이때, 아래와 같이 쿼리를 수행하는 프로그램을 작성하시오.

  • c: S의 가장 뒤에 문자 c를 추가한다. 이때, c는 알파벳 소문자이다.
  • ?: S의 서로 다른 부분 문자열의 개수를 출력한다.

입력

첫째 줄에 문자열 Q가 주어진다. 문자열 Q는 쿼리를 의미하며, 쿼리를 한 줄로 합친 문자열이다. 문자열은 알파벳 소문자 또는 ?로만 이루어져 있고, 길이는 200,000을 넘지 않는다.

출력

?가 주어질 때마다, S의 서로 다른 부분 문자열의 개수를 출력한다.

예제 입력 1

aba?

예제 출력 1

5

예제 입력 2

?z?z?z?

예제 출력 2

0
1
2
3

예제 입력 3

abc?abc?

예제 출력 3

6
15

출처