알고리즘/문자열
2021. 2. 17.
Aho–Corasick
문자열 \(S\)에서 하나의 문자열을 검색하는 것은 간단합니다. 그런데 검색해야 할 문자열이 여러개라면 어떨까요? 일반적인 문자열 탐색 알고리즘으로는 이를 빠르게 처리할 수 없으므로, 다른 방법을 생각해 내야 합니다. 문자열 \(S\)가 있고, 크기가 \(n\)인 문자열의 집합 \(T\)가 있습니다. \(S\)에서 \(T\)에 속한 문자열 중 적어도 하나를 검색할 수 있는지 여부를 알고 싶습니다. \(T\)의 크기가 1이라면, 우리는 KMP알고리즘을 이용해 \(O(|S|+|T|)\)에 검색이 가능하다는 것을 알고 있습니다. anz1217.tistory.com/56 KMP 대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 ..
