LPS

[Algorithm][KMP] 28. Find the Index of the First Occurrence in a String

KMP 알고리즘이란? 문자열을 한개씩 비교하는 것이 아니라 지금까지 비교한 문자열 중 접두사, 접미사가 같을 경우 중간 과정을 생략하고 비교하는 알고리즘 시간 복잡도 \( O(n + m) \) 문제 링크 https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/ 이번 문제는 주어진 문자열에서 sub 문자열이 몇번 째 index에 존재하는지를 답안으로 내야합니다. 단순하게 생각하면 단순 문자열 비교로 보일 수 있지만, 주어진 조건을 보면 문자열의 길이가 10000입니다. 그래서 단순 비교를 한다면 당연히 시간초과가 발생합니다. 단순 전체 비교 방법 우선 단순 비교로 문제를 푸는 방법을 소개하겠습니다. 전체 문자열의 시작..