목록2025/05/14 (1)

복잡한뇌구조마냥

[알고리즘] 아호 코라식 (Aho-Corasick)

여러개의 문자열 패턴을 단순하게 순회하면서 비교해서는 알고리즘 문제의 시간초과를 감당할 수 없어서 찾은 알고리즘 방식이아호 코라식이다. Aho-Corasick 알고리즘- 여러개의 문자열 패턴을 한 번에 빠르게 텍스트에서 찾을 수 있게 해주는 알고리즘이다. - 해당 알고리즘은 간단하게 얘기하면 KMP + Trie + BFS 가 결합된 구조로, 여러패턴을 동시에 검색할 수 있는 효율적인 알고리즘이다. - 비교하고 싶은 문자열이 여러개일 때, 트라이 구조로 패턴 문자를 삽입하여 비교한다. 원리를 많이 설명하는데 해당 사진을 많이 사용해서 참고자료로 가져와봤다.- 노드가 처음시작할 때 h냐 s냐에 따라 갈 수 있는 방향이 다음과 같이 정해진다.- 만약에 he에서 글자가 끝나지만 찾는 문자가 hers라면 rs까..
공통/알고리즘 및 코딩테스트 2025. 5. 14. 03:54
이전 Prev 1 Next 다음