1/20
Loading...
🔍KMP 알고리즘
텍스트에서 패턴을 찾는 효율적인 알고리즘! 🎯 목표: 'ABAB' 패턴 찾기 ⏱️ 시간복잡도: O(n+m) 핵심 아이디어: 불일치 시 처음부터 다시 비교하지 않고, LPS 배열을 이용해 스킵!
Loading...
텍스트에서 패턴을 찾는 효율적인 알고리즘! 🎯 목표: 'ABAB' 패턴 찾기 ⏱️ 시간복잡도: O(n+m) 핵심 아이디어: 불일치 시 처음부터 다시 비교하지 않고, LPS 배열을 이용해 스킵!
KMP(Knuth-Morris-Pratt) 알고리즘은 텍스트에서 패턴을 찾을 때 불필요한 비교를 건너뛰어 O(n+m) 시간에 검색하는 알고리즘입니다. LPS(Longest Proper Prefix-Suffix) 배열을 활용합니다.