| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436462 | Theoretical Computer Science | 2006 | 7 Pages |
Abstract
A square is a string that can be divided into two identical substrings. The problem of square detection has found applications in areas such as bioinformatics and data compression. There are many offline algorithms for the problem. In this paper, we give the first online algorithm for deciding whether a string contains a square. Our algorithm runs in total time where h is the length of the longest prefix of the input string that does not contain a square.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
