16907번 - 서로 다른 부분 문자열 쿼리 2

문제

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

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

입력

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

출력

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

제한

힌트