시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 158 | 44 | 29 | 25.893% |
알파벳 대문자로만 이루어진 문자열 S가 있고, 길이는 N이다. S[i]는 S의 i번째 문자를 나타내고, S[i:j]는 S[i], S[i+1], ..., S[j-1], S[j]에 해당하는 S의 부분 문자열을 나타낸다. 이 문제에서 사용하는 문자열의 인덱스는 1부터 시작한다.
U(i, j)는 S[i:j]에 나타나는 알파벳을 순서대로 정렬한 문자열을 의미하고, 중복해서 나타나는 알파벳은 제외한다.
예를 들어, S = "ABCBA" 인 경우 U(1, 3) = "ABC"가 되며, U(2, 4) = "BC", U(1, 5) = "ABC"이다.
모든 1 ≤ i ≤ j ≤ N에 대하여 U(i, j)을 구했을 때 이 문자열 중에서 서로 다른 문자열이 모두 몇 개 있는지 구해보자.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 문자열 S가 주어진다.
각 테스트 케이스에 대해서 U(i, j)에 서로 다른 문자열이 몇 개 있는지 출력한다.
4 AAA ABCBA ABABAB ABCXYZABC
1 6 3 30
두 번째 예제의 경우 A, B, C, AB, BC, ABC 총 여섯 개의 문자열이 존재한다.
세 번째 예제의 경우 A, B, AB 총 세 개의 문자열이 존재한다.