흙금이네 블로그

아이디어 KMP 알고리즘을 이용해 문자열 T에서 P를 찾을 때마다 그 위치를 추가해 나간다. 풀이 첫 번째 for문에서 문자열 P에서 접두사와 접미사가 일치하는 최대 길이를 투 포인터로 찾고 리스트 lps에 저장한다. i와 j가 가리키는 두 문자가 같으면 그 길이를 lps에 저장하고, 그렇지 않으면 lps를 참조해 비교할 문자 인덱스를 조정한다. lps에 저장된 길이가 곧 일치하는 부분 문자열 이후의 인덱스를 나타내므로 패턴이 일치한 부분은 비교를 건너뛸 수 있다. 두 번째 for문에서도 같은 방법으로 문자열 T에서 문자열 P를 찾고 P를 찾으면 그 위치를 리스트 idx_list에 추가한다. T = input() P = input() N, M = len(T), len(P) lps = [0]*M j = 0..