{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:55:09Z","timestamp":1787385309343,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540557197","type":"print"},{"value":"9783540472780","type":"electronic"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55719-9_82","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:34:35Z","timestamp":1330252475000},"page":"296-307","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Optimal parallel algorithms for periods, palindromes and squares"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dany","family":"Breslauer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zvi","family":"Galil","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"24_CR1","unstructured":"Apostolico, A. (1991), Optimal parallel detection of squares in strings, CSTR-91-026, Purdue and Algorithmica, in press."},{"key":"24_CR2","unstructured":"Apostolico, A. and Breslauer D. (1991), An optimal O(loglogn) time parallel algorithm for detecting all repetitions in a string, In preparation."},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"Apostolico, A. and Preparata, F. P. (1983), Optimal off-line detection of repetitions in a string, Theoretical Computer Science 22, 297\u2013315.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"24_CR4","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/65950.65958","volume":"36","author":"P. Beame","year":"1989","unstructured":"Beame, P., and Hastad, J. (1989), Optimal Bound for Decision Problems on the CRCW PRAM, Journal of ACM 36:3, 643\u2013670.","journal-title":"Journal of ACM"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321812.321815","volume":"81","author":"R. P. Brent","year":"1974","unstructured":"Brent, R. P. (1974), The parallel evaluation of general arithmetic expressions, J. ACM 81, 201\u2013206.","journal-title":"J. ACM"},{"issue":"6","key":"24_CR6","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1137\/0219072","volume":"19","author":"D. Breslauer","year":"1990","unstructured":"Breslauer, D. and Galil, Z. (1990), An optimal O(log logn) parallel string matching algorithm, SIAM J. Comput. 19:6, 1051\u20131058.","journal-title":"SIAM J. Comput."},{"key":"24_CR7","unstructured":"Breslauer, D. and Galil, Z. (1991), A lower bound for parallel string matching, Proc. 23rd ACM Symp. on Theory of Computation, 439\u2013443."},{"key":"24_CR8","unstructured":"Breslauer, D. and Galil Z. (1991), Finding all the periods and initial palindromes of a string in parallel, manuscript."},{"issue":"5","key":"24_CR9","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M. Crochemore","year":"1981","unstructured":"Crochemore, M. (1981), An optimal algorithm for computing the repetitions in a word, Information Processing Letters 12:5, 244\u2013250.","journal-title":"Information Processing Letters"},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M. (1986), Transducer and repetitions, Theoretical Computer Science 45, 63\u201386.","journal-title":"Theoretical Computer Science"},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0304-3975(91)90073-B","volume":"88","author":"M. Crochemore","year":"1991","unstructured":"Crochemore, M. and Rytter, W. (1991), Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays, Theoretical Computer Science 88, 59\u201382.","journal-title":"Theoretical Computer Science"},{"key":"24_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(91)90223-5","volume":"38","author":"M. Crochemore","year":"1991","unstructured":"Crochemore, M. and Rytter, W. (1991), Efficient Parallel Algorithms to Test Square-freeness and Factorize Strings, Information Processing Letters 38, 57\u201360.","journal-title":"Information Processing Letters"},{"key":"24_CR13","unstructured":"Fich, F. E., Ragde, R. L., and Wigderson, A. (1984), Relations between concurrent-write models of parallel computation, Proc. 3rd ACM Symp. on Principles of Distributed Computing, 179\u2013189."},{"key":"24_CR14","first-page":"113","volume":"7","author":"M. J. Fischer","year":"1974","unstructured":"Fischer, M. J. and Paterson, M. S. (1974), String-Matching and other products, SIAM-AMS proceedings, Vol 7, 113\u2013125.","journal-title":"SIAM-AMS proceedings"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0206024","volume":"6","author":"D. E. Knuth","year":"1977","unstructured":"Knuth, D. E., Morris, J. H. and Pratt, V. R. (1977), Fast pattern matching in strings, SIAM J. Comput. 6, 322\u2013350.","journal-title":"SIAM J. Comput."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"R. C. Lyndon","year":"1962","unstructured":"Lyndon, R. C. and Schutzenberger, M. P. (1962), The equation a\n\n                  M\n                \n\u2014 b\n\n                  N\n                \nc\n\n                  P\n                 in a free group, Michigan Math. J. 9, 289\u2013298.","journal-title":"Michigan Math. J."},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"G. M. Main","year":"1984","unstructured":"Main, G. M. and Lorentz, R. J. (1984), An O(n log n) algorithm for finding all repetitions in a string, Journal of Algorithms 5, 422\u2013432.","journal-title":"Journal of Algorithms"},{"key":"24_CR18","unstructured":"Main, G. M. and Lorentz, R. J. (1985), Linear time recognition of squarefree strings, in Combinatorial Algorithms on Words, Edited by A. Apostolico and Z. Galil, 271\u2013278."},{"key":"24_CR19","unstructured":"Thue, A. (1906), \u00dcber unendliche Zeichenreihen, Norske Vid. Selse. Skr. Mat. Nat Kl. (Cristiania), Nr. 7, 1\u201322."},{"key":"24_CR20","first-page":"1","volume":"Nr. 1","author":"A. Thue","year":"1912","unstructured":"Thue, A. (1912), \u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk Skr. Mat. Nat. Kl. (Cristiania), Nr. 1, 1\u201367.","journal-title":"Norske Vid. Selsk Skr. Mat. Nat. Kl. (Cristiania)"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0019-9958(85)80028-0","volume":"67","author":"U. Vishkin","year":"1985","unstructured":"Vishkin, U. (1985), Optimal parallel pattern matching in strings, Information and Control 67, 91\u2013113.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55719-9_82","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:22:48Z","timestamp":1578536568000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55719-9_82"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557197","9783540472780"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-55719-9_82","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}