문제에서 N,M의 범위가 10000 이다. 완전탐색을 한다고 하면 O(NM단어 및 문자의 길이) 이므로 절대 풀 수 없다.
그러므로 특수한 방식의 전처리를 해야하는데 단어의 길이가 가변적이므로 n차원 리스트에 저장하는 것 또한 쉽지않다.
문제에서 첫글자,마지막글자를 제외한 가운데 글자들은 순서가 상관이 없다고 한다.
그렇기 때문에 우리는 각각의 알파벳이 몇개 있는지만 신경쓰면 된다.
그러므로 나는 가운데 문자열을 정렬하여 표기해보았다.
예를 들어 예제입력의 사전에 있는 단어들을
{
'aa': {
'abb': 2,
'abc': 1
}
}
과 같이 표현할 수 있다.
ababa 와 aabba 는 모두 가운데 문자열을 정렬했을때 'abb' 형태이기 때문에 'abb':2 와 같은 형태로 개수를 표기한 것이다.
import sys
from collections import defaultdict
input = sys.stdin.readline
dic = defaultdict(dict)
for _ in range(int(input())):
line = input().strip()
i = line[0]+line[-1] if len(line)>1 else line[0]
k = ''.join(sorted(line[1:-1]))
dic[i][k] = dic[i].get(k,0)+1
for _ in range(int(input())):
ans = 1
for line in input().strip().split():
i = line[0]+line[-1] if len(line)>1 else line[0]
k = ''.join(sorted(line[1:-1]))
ans *= dic[i].get(k,0)
print(ans)
aa : {
'' : 2
}
형태로 저장될 수 있기 때문이다. 그러므로
i = line[0]+line[-1] if len(line)>1 else line[0]
라인을 이용해 해결했다.