TY - GEN

T1 - Tighter bounds on the exact complexity of string matching

AU - Cole, Richard

AU - Hariharan, Ramesh

N1 - Publisher Copyright:
© 1992 IEEE.

PY - 1992

Y1 - 1992

N2 - The paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n + O(n/m) character comparisons, following preprocessing. Specifically, the authors show an upper bound of n+8/3(m+1)(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m2) time for preprocessing. In addition the following lower bounds are shown: for online algorithms, a bound of n+11/5(m+1) (n-m) character comparisons for m = 10 + 11 k, for any integer k >or= 1, and for general algorithms, a bound of n+2(n-m)/m+3 character comparisons, for m=2 k+l, for any integer k>or=1.

AB - The paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n + O(n/m) character comparisons, following preprocessing. Specifically, the authors show an upper bound of n+8/3(m+1)(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m2) time for preprocessing. In addition the following lower bounds are shown: for online algorithms, a bound of n+11/5(m+1) (n-m) character comparisons for m = 10 + 11 k, for any integer k >or= 1, and for general algorithms, a bound of n+2(n-m)/m+3 character comparisons, for m=2 k+l, for any integer k>or=1.

UR - http://www.scopus.com/inward/record.url?scp=85031321354&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031321354&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1992.267791

DO - 10.1109/SFCS.1992.267791

M3 - Conference contribution

AN - SCOPUS:85031321354

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 600

EP - 609

BT - Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

PB - IEEE Computer Society

T2 - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992

Y2 - 24 October 1992 through 27 October 1992

ER -