TY - GEN
T1 - Alphabet independent two dimensional matching
AU - Amir, Amihood
AU - Benson, Gary
AU - Farach, Martin
N1 - Funding Information:
*College of Computing, Georgia Institute of Technology, Atlanta, GA 30332-0280; (404) 853-0083; amir@cc.gatecb. edu; Partially supported by NSF ~ant IR.I-90-13055. tDept. of Computer Scienee, University of Maryland, Col- lege Park, MD 20742; (301) 405-2715; benaon@cs.umd.edq Partially supported by NSF grant IRI-90-13055. :DIMACS, Box 1179, Rutgers University, 08855; (808) 932-592% farach@Xhu.acs.mtgers.edw, by DIMACS under NSF contract STC-88-09648.
Publisher Copyright:
© 1992 ACM.
PY - 1992/7/1
Y1 - 1992/7/1
N2 - There are many solutions to the string matching problem which are strictly linear in the input size and independent of alphabet size. Furthermore, the model of computation for these algorithms is very weak: they allow only simple arithmetic and comparisons of equality between characters of the input. In contrast, algorithm for two dimensional matching have needed stronger models of computation, most notably assuming a totally ordered alphabet. The fastest algorithms for two dimensional matching have therefore had a logarithmic dependence on the alphabet size. In the worst case, this gives an algorithm that runs in O(n2 log m) with O(m2 log m) preprocessing. We show an algorithm for two dimensional matching with an O(n2) text scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e. it runs on the same model as the standard linear time string matching algorithm.
AB - There are many solutions to the string matching problem which are strictly linear in the input size and independent of alphabet size. Furthermore, the model of computation for these algorithms is very weak: they allow only simple arithmetic and comparisons of equality between characters of the input. In contrast, algorithm for two dimensional matching have needed stronger models of computation, most notably assuming a totally ordered alphabet. The fastest algorithms for two dimensional matching have therefore had a logarithmic dependence on the alphabet size. In the worst case, this gives an algorithm that runs in O(n2 log m) with O(m2 log m) preprocessing. We show an algorithm for two dimensional matching with an O(n2) text scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e. it runs on the same model as the standard linear time string matching algorithm.
UR - http://www.scopus.com/inward/record.url?scp=0026992709&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026992709&partnerID=8YFLogxK
U2 - 10.1145/129712.129719
DO - 10.1145/129712.129719
M3 - Conference contribution
AN - SCOPUS:0026992709
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 59
EP - 68
BT - Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992
PB - Association for Computing Machinery
T2 - 24th Annual ACM Symposium on Theory of Computing, STOC 1992
Y2 - 4 May 1992 through 6 May 1992
ER -