×

An O(N) algorithm for finding periodicity of a sequence using hash coding. (English) Zbl 0364.68052

MSC:

68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
68N01 General topics in the theory of software
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA, (Chap. 9, Sect. 3) · Zbl 0207.01701
[2] E. Goto, T. Ida and T. Gunji, Parallel hashing algorithms, to appear in Information Processing Lett.; E. Goto, T. Ida and T. Gunji, Parallel hashing algorithms, to appear in Information Processing Lett. · Zbl 0362.68070
[3] Goto, E.; Kanada, Y., Hashing lemmas on time complexities with applications to formula manipulation, Proceedings of 1976 ACM Symposium on Symbolic and Algebraic Computation, 154-158 (1976) · Zbl 0453.68011
[4] Knuth, D. E., The Art of Computer Programming, 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA, (Sorting and Searching) · Zbl 0191.17903
[5] Morris, J. H.; Pratt, V. R., A linear pattern matching algorithm, (Technical Report No. 40 (1970), Computing Center, University of California: Computing Center, University of California Berkeley)
[6] V.R. Pratt, J.H. Morris Jr. and D.E. Knuth, Fast pattern matching in strings, to appear in SIAM J. Comput.; V.R. Pratt, J.H. Morris Jr. and D.E. Knuth, Fast pattern matching in strings, to appear in SIAM J. Comput. · Zbl 0372.68005
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.