{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:00:54Z","timestamp":1787497254716,"version":"build-2736575974"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,12,1]],"date-time":"1992-12-01T00:00:00Z","timestamp":723168000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1992,12]]},"DOI":"10.1007\/bf01758848","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T06:37:44Z","timestamp":1118903864000},"page":"285-319","source":"Crossref","is-referenced-by-count":16,"title":["Optimal parallel detection of squares in strings"],"prefix":"10.1007","volume":"8","author":[{"given":"Alberto","family":"Apostolico","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01758848_CR1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1051\/ita\/1984180201471","volume":"18","author":"A. Apostolico","year":"1984","unstructured":"A. Apostolico, On Context-Constrained Squares and Repetitions in a String,RAIRO Inform. Th\u00e9or. 18 (1984), 147\u2013159.","journal-title":"RAIRO Inform. Th\u00e9or."},{"issue":"5","key":"BF01758848_CR2","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1137\/0219066","volume":"19","author":"A. Apostolico","year":"1990","unstructured":"A. Apostolico, M. J. Atallah, L. L. Larmore, and H. S. McFaddin, Efficient Parallel Algorithms for String Editing and Related Problems,SIAM J. Comput. 19(5) (1990), 968\u2013988. Also,Proceedings of the 26th Allerton Conference on Communications, Control and Computing, Monticello, Ill., Sept. 1988, pp. 253\u2013263.","journal-title":"SIAM J. Comput."},{"key":"BF01758848_CR3","series-title":"Nato ASI Series F","volume-title":"Combinatorial Algorithms on Words","year":"1985","unstructured":"A. Apostolico and Z. Galil (eds.),Combinatorial Algorithms on Words, Nato ASI Series F, Vol. 12, Springer-Verlag, Berlin, 1985."},{"key":"BF01758848_CR4","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"A. Apostolico, C. Iliopoulos, G. Landau, B. Schieber, and U. Vishkin, Parallel Construction of a Suffix Tree, with Applications,Algorithmica 3 (1988), 347\u2013365.","journal-title":"Algorithmica"},{"key":"BF01758848_CR5","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(83)90109-3","volume":"22","author":"A. Apostolico","year":"1983","unstructured":"A. Apostolico and F. P. Preparata, Optimal Off-Line Detection of Repetitions in a String,Theoret. Comput. Sci. 22 (1983), 297\u2013315.","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"BF01758848_CR6","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1016\/0022-0000(85)90060-1","volume":"31","author":"A. Apostolico","year":"1985","unstructured":"A. Apostolico and F. P. Preparata. Structural Properties of the String Stratistics ProblemJ. Comput. System. Sci. 31(3) (1985), 394\u2013411.","journal-title":"J. Comput. System. Sci."},{"key":"BF01758848_CR7","doi-asserted-by":"crossref","unstructured":"O. Berkman, D. Breslauer, Z, Galil, B. Schieber, and U. Vishkin, Hightly Parallelizable Problems,Proceedings of the 21st ACM Symposium on Theory of Computing, Seattle, Wash., May 1989, pp. 309\u2013319.","DOI":"10.1145\/73007.73036"},{"key":"BF01758848_CR8","doi-asserted-by":"crossref","first-page":"81","DOI":"10.2307\/1970044","volume":"68","author":"K. T. Chen","year":"1958","unstructured":"K. T. Chen, R. H. Fox, and R. C. Lyndon, Free Differential Calculus, IV,Ann. of Math. 68 (1958), 81\u201395.","journal-title":"Ann. of Math."},{"issue":"5","key":"BF01758848_CR9","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M. Crochemore","year":"1981","unstructured":"M. Crochemore, An Optimal Algorithm for Computing the Repetitions in a Word,Inform. Process. Lett. 12(5) (1981), 244\u2013250.","journal-title":"Inform. Process. Lett."},{"key":"BF01758848_CR10","first-page":"781","volume":"296","author":"M. Crochemore","year":"1983","unstructured":"M. Crochemore, Recherche Linearire d'un Carr\u00e9 dans un MotC. R. Acad. Sci. Paris S\u00e9r. I 296 (1983), 781\u2013784.","journal-title":"C. R. Acad. Sci. Paris S\u00e9r. I"},{"key":"BF01758848_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0304-3975(91)90073-B","volume":"88","author":"M. Crochemore","year":"1991","unstructured":"M. Crochemore and W. Rytter, Usefulness of the Karp-Miller-Rosenberg Strategy in the Design of Parallel Algorithms,Theoret. Comput. Sci. 88 (1991), 59\u201382.","journal-title":"Theoret. Comput. Sci."},{"key":"BF01758848_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"4","author":"J. P. Duval","year":"1983","unstructured":"J. P. Duval, Factorizing Words over an Ordered Alphabet,J. Algorithms 4 (1983), 363\u2013381.","journal-title":"J. Algorithms"},{"key":"BF01758848_CR13","doi-asserted-by":"crossref","unstructured":"F. E. Fich, R. L. Ragde, and A. Wigderson, Relations between Concurrent-Write Models of Parallel Computation,Proceedings of the 3rd A CM Symposium on Principles of Distributed Computing, Vancouver, B.C., Aug. 27\u201329, 1984, pp. 179\u2013184.","DOI":"10.1145\/800222.806745"},{"key":"BF01758848_CR14","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1982","unstructured":"M. Lothaire,Combinatorics on Words, Addison-Wesley, Reading, Mass., 1982."},{"key":"BF01758848_CR15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"R. C. Lyndon","year":"1962","unstructured":"R. C. Lyndon and M. P. Shutzenberger, The Equationa M = b N c P in a Free Group,Michigan Math. J. 9 (1962), 289\u2013298.","journal-title":"Michigan Math. J."},{"key":"BF01758848_CR16","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M. G. Main","year":"1985","unstructured":"M. G. Main and R. J. Lorentz, AnO(n logn) Algorithm for Finding all Repetitions in a String,J. Algorithms 5 (1985), 422\u2013432.","journal-title":"J. Algorithms"},{"key":"BF01758848_CR17","series-title":"Nato ASI Series F","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/978-3-642-82456-2_18","volume-title":"Combinatorial Algorithms on Words","author":"M. G. Main","year":"1985","unstructured":"M. G. Main and R. J. Lorentz, Linear-Time Recognition of Square-Free Strings, inCombinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Nato ASI Series F, Vol. 12, Springer-Verlag, Berlin, 1985, pp. 271\u2013278."},{"key":"BF01758848_CR18","series-title":"Nato ASI Series F","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/978-3-642-82456-2_19","volume-title":"Combinatorial Algorithms on Words","author":"M. Rabin","year":"1985","unstructured":"M. Rabin, Discovering Repetitions in Strings, inCombinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds), Nato ASI Series F, Vol. 12, Springer-Verlag, Berlin, 1985, pp. 279\u2013288."},{"key":"BF01758848_CR19","first-page":"1","volume":"no. 7","author":"A. Thue","year":"1906","unstructured":"A. Thue, \u00dcber unendliche Zeichenreihen,Norske Vid. Selsk. I Mat. Natur. Kl. Skr., Christiania no. 7 (1906), 1\u201322.","journal-title":"Norske Vid. Selsk. I Mat. Natur. Kl. Skr."},{"key":"BF01758848_CR20","first-page":"1","volume":"no. 1","author":"A. Thue","year":"1912","unstructured":"A. Thue, \u201c\u00dcber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen\u201d,Norske Vid. Selsk. I Mat.-Natur. Kl. Skr., Christiania no. 1 (1912), 1\u201367.","journal-title":"Norske Vid. Selsk. I Mat.-Natur. Kl. Skr."},{"issue":"1","key":"BF01758848_CR21","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/321921.321923","volume":"23","author":"C. K. Wong","year":"1976","unstructured":"C. K. Wong and A. K. Chandra, Bounds for the String Editing Problem,J. Assoc. Comput. Mach. 23(1) (1976), 13\u201316.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758848.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758848\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758848","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T15:26:51Z","timestamp":1586273211000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758848"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":21,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["BF01758848"],"URL":"https:\/\/doi.org\/10.1007\/bf01758848","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}