정렬 + 문자열

접두사 찾기

접두사
이 문제와 비슷하나 시간 제한이 1초 이므로 비교할 단어의 인덱스를 찾아가서 거기서 부터 비교하면서 시간을 줄이는 것이 중요합니다.

검사해야 할 문자열을 돌면서 집합 S에 포함되어 있으면 카운트를 증가시키고 종료합니다. 이 때 집합 S에 포함되어 있는지 확인하는 과정에서 단어의 맨 앞자리만을 나타내는 배열을 만들어 그 배열의 인덱스를 찾아서 거기서 부터 탐색합니다.

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
lst = []
compare = []
for i in range(n):
	lst.append(sys.stdin.readline().rstrip())
for i in range(m):
	compare.append(sys.stdin.readline().rstrip())
lst.sort(key=lambda x:len(x))
compare.sort()
tmp = []
for i in lst:
	tmp.append(i[0])
cnt = 0
flag = 0
for i in range(len(compare)):
	try:
		for j in range(tmp.index(compare[i][0]), len(lst)):
			if lst[j].startswith(compare[i]):
				cnt += 1
				break
	except:
		continue

print(cnt)