AC自动机算法1975

在计算机科学中，艾侯-科拉希克算法 是由阿尔佛雷德·艾侯和玛格丽特·J·科拉希克 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配，算法的时间复杂度会近似于匹配的二次函数。