TY - GEN
T1 - Fully compressed pattern matching algorithm for balanced straight-line programs
AU - Hirao, M.
AU - Shinohara, A.
AU - Takeda, M.
AU - Arikawa, S.
PY - 2000/1/1
Y1 - 2000/1/1
N2 - We consider a fully compressed pattern matching problem, where both text T and pattern P are given by its succinct representation, in terms of straight-line programs and its variant. The length of the text T and pattern P may grow exponentially with respect to its description size n and m, respectively. The best known algorithm for the problems runs in O(n2m2) time using O(nm) space. The authors introduce a variant of straight-line programs, called balanced straight-line programs so that we establish a faster fully compressed pattern matching algorithm. Although the compression ratio of balanced straight-line programs may be worse than the original straight-line programs, they can still express exponentially long strings. Our algorithm runs in O(nm) time using O(nm) space.
AB - We consider a fully compressed pattern matching problem, where both text T and pattern P are given by its succinct representation, in terms of straight-line programs and its variant. The length of the text T and pattern P may grow exponentially with respect to its description size n and m, respectively. The best known algorithm for the problems runs in O(n2m2) time using O(nm) space. The authors introduce a variant of straight-line programs, called balanced straight-line programs so that we establish a faster fully compressed pattern matching algorithm. Although the compression ratio of balanced straight-line programs may be worse than the original straight-line programs, they can still express exponentially long strings. Our algorithm runs in O(nm) time using O(nm) space.
UR - http://www.scopus.com/inward/record.url?scp=84964523963&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964523963&partnerID=8YFLogxK
U2 - 10.1109/SPIRE.2000.878188
DO - 10.1109/SPIRE.2000.878188
M3 - Conference contribution
AN - SCOPUS:84964523963
T3 - Proceedings - 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000
SP - 132
EP - 138
BT - Proceedings - 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th International Symposium on String Processing and Information Retrieval, SPIRE 2000
Y2 - 27 September 2000 through 29 September 2000
ER -