查看文章

We introduce a new matching criterion — function matching — that captures several different applications. The function matching. problem has as its input a text T of length n over alphabet Σ_T and a pattern P = P[1]P[2] ... P[m] of length m over alphabet Σ_T. We seek all text locations i for which, for some function f: Σ_T → Σ_T (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2]) ... f(P[m]).

We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \frac{1} {{n^k }} $$\end{document} of declaring a false positive.W e give a deterministic algorithm …