<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-241

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Richard Cole, Ramesh Hariharan, M.S. Paterson and U. Zwick, Tighter Lower Bounds on The Exact Complexity of String Matching (March 1, 1993).

Abstract

The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms, a lower bound of about (1 + 16/(7m + 16)) mod n character comparisons is obtained. For general algorithms, a lower bound of about (1+ 2/(m + 3)) mod n character comparisons is obtained. These lower bounds complement an on-line upper bound of about (1 + 8/(3m + 3)) mod n comparisons obtained recently by Cole and Hariharan. The lower bounds are obtained by finding patterns with interesting combinatorial properties. It is also shown that for some patterns off-line algorithms can be more efficient than on-line algorithms.

<%@ include file="cited.html" %>

Richard Cole, Ramesh Hariharan, M.S. Paterson and U. Zwick, "Tighter Lower Bounds on The Exact Complexity of String Matching", SIAM Journal on Computing 24(1), pp. 30-45 (1995)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>