×
Apostolico, A.; Preparata, F. P.

Optimal off-line detection of repetitions in a string. (English) Zbl 0497.68052

Theor. Comput. Sci. 22, 297-315 (1983).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0497.68052

Cited in 67 Documents

MSC:

68T99 Artificial intelligence

Keywords:

algorithm; repetitions in a given textstring on a finite alphabet; leaf- tree
PDF BibTeX XML Cite
\textit{A. Apostolico} and \textit{F. P. Preparata}, Theor. Comput. Sci. 22, 297--315 (1983; Zbl 0497.68052)
Full Text: DOI

References:

[1] Aho, A. V.; Hoperoft, J. F.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA
[2] Apostolico, A., Fast applications of suffix trees, (Lainiotis, D. G.; Tzannes, N. S., Advances in Control (1980), D. Reidel: D. Reidel Dordrecht, Netherlands), 558-567
[3] Braunholtz, C. H., Solution to Problem 5030, Ann. of Math., 70, 675-676 (1963)
[4] Crochemore, M., An optimal algorithm for computing the repetitions in a word, Information Processing Lett., 12, 5, 244-250 (1981) · Zbl 0467.68075
[5] Duval, J. P., Sur la périodicité des mots, (Thése de Docteur du 3me cycle (1978), Faculty of Sciences, University of Rouen) · Zbl 0482.68078
[6] Fine, N. J.; Wilf, H. S., Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16, 109-114 (1965) · Zbl 0131.30203
[7] Harrison, M. A., (Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA), 36-40
[8] Hedlund, G. A., Remarks on the work of Axel Thue on sequences, Nord. Mat. Tidskr., 15, 148-150 (1967) · Zbl 0153.33101
[9] Knuth, D. E., The Art of Computer Programming, Vol 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[10] Knuth, D. E.; Morris, J. H.; Pratt, V. R., Fast pattern matching in strings, SIAM J. Comput., 6, 323-350 (1977) · Zbl 0372.68005
[11] Lentin, A.; Schützenberger, M. P., A combinatorial problem in the theory of free monoids, Proc. University of North Carolina, 128-144 (1967)
[12] Lyndon, R. C.; Schützenberger, M. P., The equation \(a^M=b^NC^{P\) · Zbl 0106.02204
[13] Main, M.; Lorentz, R., An \(O(n\) log \(n)\) algorithm for finding repetition in a string, (T.R. 79-056 (1979), Computer Science Department, Washington State University: Computer Science Department, Washington State University Pullman)
[14] McCreight, E. M., A space economical suffix tree construction algorithm, J. ACM, 23, 262-272 (1976) · Zbl 0329.68042
[15] Peterson, M.; Hewitt, C. E., Comparative schematology, (Proc. MAC Conference on Concurrent Systems and Parallel Computation (1970), Woods Hole: Woods Hole MA), 119-127 · Zbl 0401.68002
[16] Thue, A., Über die gegenseitige Lage gleicher Teile Gewisser Zeichenreichen, Skr. Vid.-Kristiana I. Mat. Naturv. Klasse, 1, 1-67 (1912) · JFM 44.0462.01
[17] Weiner, P., Linear pattern matching algorithms, Proc. 14th Annual Symposium on Switching and Automata Theory, 1-11 (1973)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.