라빈카프
-
KMP, 라빈 카프 알고리즘공부/알고리즘 2021. 6. 15. 16:43
백준 5525번 풀다가 모르겠어서 질문 검색란 보니 요런 알고리즘이 있길래 정리 https://www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문자열 검색 시 가장 간단한 방법을 생각해보자면 한자리씩 옮겨가면서 비교하는 방법이 떠오를 것 백준 문제를 예시로 들어보자 O O I O I O I O I I O I I I O I OOI!=IOI 불일치 O O I O I O I O I I O I I I O I OIO!=IOI 불일치 O O I O I O I O I I O I I I O I IO..