Skip to content

ahoCorasick ​

Busca todos os padrões em um texto e retorna pares [endIndex, patternIndex]. endIndex é o offset byte inclusivo da correspondência; os pares são ordenados por offset final e depois por índice do padrão.

tyrus
import { ahoCorasick } from "tyrus:algorithm";

const matches: [usize, usize][] = ahoCorasick("ababa", ["aba", "ba"]);
print(matches[0][0], matches[0][1]); // 2 0

Resultado de estudo ​

tyrus
interface AhoCorasickInfo {
    text: string;
    patterns: string[];
    matches: [usize, usize][];
    visitedStates: usize[];
    transitionCount: usize;
    failureFollowCount: usize;
}
tyrus
import { AhoCorasickInfo, ahoCorasickInfo } from "tyrus:algorithm";

const info: AhoCorasickInfo = ahoCorasickInfo("ababa", ["aba", "ba"]);
print(info.text); // ababa
print(info.patterns); // [aba, ba]
print(info.matches); // [[2, 0], [2, 1], [4, 0], [4, 1]]
print(info.visitedStates); // [1, 2, 3, 2, 3]
print(info.transitionCount); // 5
print(info.failureFollowCount); // 2

O resultado de estudo armazena um estado do autômato para cada byte de entrada. Seu armazenamento adicional é O(n + p), onde n é o tamanho do texto e p é o tamanho total dos padrões.

O autômato executa em O(tamanho do texto + soma dos tamanhos dos padrões + número de correspondências) e usa espaço auxiliar O(soma dos tamanhos dos padrões).