Periods in strings
作者： Leo J Guibas , Andrew M Odlyzko
DOI: 10.1016/0097-3165(81)90038-8
关键词: Empty string 、 String kernel 、 String searching algorithm 、 Generating function 、 Discrete mathematics 、 Set (abstract data type) 、 Approximate string matching 、 Order (ring theory) 、 Mathematics 、 Combinatorics 、 String (computer science)
摘要: Abstract In this paper we explore the notion of periods a string. A period can be thought as shift that causes string to match over itself. We obtain two sets necessary and sufficient conditions for set integers some (what call correlation string). show number distinct correlations length n is independent alphabet size order nlogn. By using generating function methods enumerate strings having given correlation, investigate certain related questions.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(9)
R. C. Lyndon, M. P. Schützenberger, R. C. Lyndon, The equation $a^M=b^Nc^P$ in a free group. Michigan Mathematical Journal. ,vol. 9, pp. 289- 298 ,(1962) , 10.1307/MMJ/1028998766
Leo J. Guibas, Andrew M. Odlyzko, A new proof of the linearity of the Boyer-Moore string searching algorithm 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 189- 195 ,(1977) , 10.1109/SFCS.1977.3
Donald E Knuth, James H Morris, Jr, Vaughan R Pratt, Fast Pattern Matching in Strings SIAM Journal on Computing. ,vol. 6, pp. 323- 350 ,(1977) , 10.1137/0206024
L.J Guibas, A.M Odlyzko, String overlaps, pattern matching, and nontransitive games Journal of Combinatorial Theory, Series A. ,vol. 30, pp. 183- 208 ,(1981) , 10.1016/0097-3165(81)90005-4
N. J. Fine, H. S. Wilf, Uniqueness theorems for periodic functions Proceedings of the American Mathematical Society. ,vol. 16, pp. 109- 114 ,(1965) , 10.1090/S0002-9939-1965-0174934-9
Zvi Galil, Joel Seiferas, Saving space in fast string-matching 18th Annual Symposium on Foundations of Computer Science (sfcs 1977). pp. 179- 188 ,(1977) , 10.1109/SFCS.1977.27
P. Nielsen, On the expected duration of a search for a fixed pattern in random data (Corresp.) IEEE Transactions on Information Theory. ,vol. 19, pp. 702- 704 ,(1973) , 10.1109/TIT.1973.1055064
Robert S. Boyer, J. Strother Moore, A fast string searching algorithm Communications of the ACM. ,vol. 20, pp. 762- 772 ,(1977) , 10.1145/359842.359859
Peter Tolstrup Nielsen, On the expected duration of a search for a fixed pattern in random data I E E E Transactions on Information Theory. ,vol. 19, pp. 702- 704 ,(1973)