O (N)의 문자열 내의 부분 문자열 발생 수

Question

건초 더미에서 선형 시간으로 각 바늘의 수를 계산하는 방법을 궁금해하고있었습니다. 나는 Aho-Corasick 알고리즘을 사용할 것이라고 생각했지만 시간 복잡성은 바늘의 발생 횟수에 의존하기를 원하지 않습니다.

Answer 1

문자열 세트를 검색하고 발생 횟수에 의존하지 않으려면 Rabin–Karp을 사용하십시오. 평균/최고 경우 실행 시간은 O(n + m)이지만 최악의 경우는 O (nm)입니다. 여기서 n은 텍스트 길이이고 m은 검색 패턴 길이를 합한 것입니다.

당신이 n 텍스트의 길이와 k 검색 패턴의 길이 복잡 O(n + k)와 Knuth–Morris–Pratt을 사용할 수있는 하나의 문자열을 검색합니다.

Answer 2

전체 발생 횟수 만 있으면 (그리고 위치 자체는 신경 쓰지 않아도됩니다.) Aho-Corasick을 효율적으로 사용할 수 있습니다. 우리가 현재 노드 v에 있다고 가정합시다. 얼마나 많은 하위 문자열이 현재 위치에서 끝나야합니다. 필자는 정확히 접미사 링크로 v에서 도달 할 수있는 터미널 노드의 수라고 주장합니다. 그러나 접미사 링크는 나무를 형성합니다. 따라서 접미어 링크로 구성된 트리의 루트에 v의 경로에있는 터미널 정점 수를 계산해야합니다. 선형 전처리를 사용하여 시간을 계산할 수 있습니다 (예 :이 트리를 명시 적으로 빌드하고 깊이 우선 검색을 사용하여 루트에서 모든 정점으로의 선형 시간에 대한 합계를 계산할 수 있음). 올바른 순서로 정점을 처리 할 수도 있습니다 (예 : 높이의 증가 순서). sum[v] += sum[suffix_link(v)]과 같은 작업을 수행 할 수 있습니다. 이 경우 실제로이 트리를 작성할 필요조차 없습니다.

이 알고리즘은 입력의 크기가 선형 시간에 분명히 작동합니다 (Aho-Corasick 자동 완성을 작성하고 직선 시간에 "접미어 링크 경로"의 합계를 계산 한 다음 일반적으로하는 것처럼 자동 연산을 사용합니다) .