모든 문자열에 값을 매핑하면서도 탐색을 충분히 빠르게 할 수 있을까?
모든 문자열을 정수에 대응하는 맵 과 빈 문자열 를 가지고 있다. 처음에 은 모든 문자열을 에 대응하고 있다.
다음 종류의 쿼리를 수행하는 프로그램을 작성하라.
1 : 뒤에 문자 를 추가한다. 는 알파벳 소문자만 주어진다.2: 의 맨 뒤에서 개의 문자를 지운다. 가 빈 문자열인 경우 아무 일도 하지 않는다.첫째 줄에 쿼리의 수 가 주어진다.
둘째 줄부터 개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.
번 쿼리가 주어질 때마다 를 출력하라.
3 : 에 를 더한다. 4: 를 출력한다.5: 뒤에 를 추가한다.4번 쿼리는 하나 이상 주어진다.