서로 다른 부분 문자열 쿼리 2
시간 제한1초메모리 제한512 MB
문자를 덧붙이는 연산과 지금까지 만든 문자열의 서로 다른 부분 문자열 개수를 묻는 질의를 순서대로 처리한다.
문제
비어 있는 문자열 가 있다. 다음 두 종류의 쿼리를 순서대로 수행하는 프로그램을 작성하시오.
c: 의 맨 뒤에 문자c를 추가한다.c는 알파벳 소문자이다.?: 의 서로 다른 부분 문자열의 개수를 출력한다.
입력
첫째 줄에 문자열 가 주어진다. 는 수행할 쿼리들을 순서대로 이어 붙인 문자열이다. 는 알파벳 소문자와 ?로만 이루어져 있으며 길이는 을 넘지 않는다. 에 포함된 ?의 개수는 한 개 이상이다.
출력
?가 나올 때마다 의 서로 다른 부분 문자열의 개수를 한 줄에 하나씩 출력한다.