{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:09Z","timestamp":1759637589985},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T00:00:00Z","timestamp":1441238400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"PSC-CUNY","award":["65112-0043"],"award-info":[{"award-number":["65112-0043"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00453-015-0065-z","type":"journal-article","created":{"date-parts":[[2015,9,3]],"date-time":"2015-09-03T14:19:15Z","timestamp":1441289955000},"page":"116-133","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["2D Lyndon Words and Applications"],"prefix":"10.1007","volume":"77","author":[{"given":"Shoshana","family":"Marcus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,3]]},"reference":[{"issue":"6","key":"65_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"65_CR2","unstructured":"Amir, A., Benson, G.: Two-dimensional periodicity and its applications. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 440\u2013452 (1992)"},{"issue":"1","key":"65_CR3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/S0097539795298321","volume":"27","author":"A Amir","year":"1998","unstructured":"Amir, A., Benson, G.: Two-dimensional periodicity in rectangular arrays. SIAM J. Comput. 27(1), 90\u2013106 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"65_CR4","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1137\/S0097539792226321","volume":"23","author":"A Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two-dimensional pattern matching. SIAM J. Comput. 23(2), 313\u2013323 (1994)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"65_CR5","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(92)90206-B","volume":"44","author":"A Amir","year":"1992","unstructured":"Amir, A., Farach, M.: Two-dimensional dictionary matching. Inf. Process. Lett. 44(5), 233\u2013239 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"65_CR6","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF01191471","volume":"28","author":"A Apostolico","year":"1995","unstructured":"Apostolico, A., Crochemore, M.: Fast parallel Lyndon factorization with applications. Math. Syst. Theory 28(2), 89\u2013108 (1995)","journal-title":"Math. Syst. Theory"},{"key":"65_CR7","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","volume":"7","author":"TJ Baker","year":"1978","unstructured":"Baker, T.J.: A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comput. 7, 533\u2013541 (1978)","journal-title":"SIAM J. Comput."},{"key":"65_CR8","doi-asserted-by":"crossref","unstructured":"Bannai, H., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: A new characterization of maximal repetitions by Lyndon trees. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 562\u2013571 (2015)","DOI":"10.1137\/1.9781611973730.38"},{"issue":"5","key":"65_CR9","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"6","author":"RS Bird","year":"1977","unstructured":"Bird, R.S.: Two dimensional pattern matching. Inf. Process. Lett. 6(5), 168\u2013170 (1977)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"65_CR10","first-page":"611","volume":"8","author":"M Chemillier","year":"2004","unstructured":"Chemillier, M.: Periodic musical sequences and Lyndon words. Soft Comput. 8(9), 611\u2013616 (2004)","journal-title":"Soft Comput."},{"key":"65_CR11","doi-asserted-by":"crossref","unstructured":"Choi, Y., Lam, T.-W.: Two-dimensional dynamic dictionary matching. In: International Symposium on Symbolic and Algebraic Computation (ISAAC), pp. 85\u201394 (1996)","DOI":"10.1007\/BFb0009484"},{"issue":"3","key":"65_CR12","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1137\/S0097539795280068","volume":"27","author":"M Crochemore","year":"1998","unstructured":"Crochemore, M., Gasieniec, L., Hariharan, R., Muthukrishnan, S., Rytter, W.: A constant time optimal parallel algorithm for two-dimensional pattern matching. SIAM J. Comput. 27(3), 668\u2013681 (1998)","journal-title":"SIAM J. Comput."},{"key":"65_CR13","first-page":"225","volume":"35","author":"M Crochemore","year":"2000","unstructured":"Crochemore, M., Iliopoulos, C., Korda, M., Reid, J.: A failure function for multiple two-dimensional pattern matching. Comb. Math. Comb. Comput. 35, 225\u2013238 (2000)","journal-title":"Comb. Math. Comb. Comput."},{"issue":"16","key":"65_CR14","doi-asserted-by":"crossref","first-page":"2812","DOI":"10.1093\/bioinformatics\/bth335","volume":"20","author":"O Delgrange","year":"2004","unstructured":"Delgrange, O., Rivals, E.: Star: an algorithm to search for tandem approximate repeats. Bioinformatics 20(16), 2812\u20132820 (2004)","journal-title":"Bioinformatics"},{"issue":"2","key":"65_CR15","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.jnt.2006.10.017","volume":"125","author":"B Farhi","year":"2007","unstructured":"Farhi, B.: Nontrivial lower bounds for the least common multiple of some finite sequences of integers. J. Number Theory 125(2), 393\u2013411 (2007)","journal-title":"J. Number Theory"},{"issue":"3","key":"65_CR16","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(78)90002-X","volume":"23","author":"H Fredricksen","year":"1978","unstructured":"Fredricksen, H., Maiorana, J.: Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Math. 23(3), 207\u2013210 (1978)","journal-title":"Discrete Math."},{"issue":"3","key":"65_CR17","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1137\/S0097539792231982","volume":"24","author":"R Giancarlo","year":"1995","unstructured":"Giancarlo, R.: A generalization of the suffix tree to square matrices, with applications. SIAM J. Comput. 24(3), 520\u2013562 (1995)","journal-title":"SIAM J. Comput."},{"key":"65_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"65_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Landau, G.M., Schieber, B.: An efficient algorithm for the all pairs suffix\u2013prefix problem. Inf. Process. Lett. 41(4), 181\u2013185 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"65_CR20","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/inco.1995.1030","volume":"117","author":"RM Idury","year":"1995","unstructured":"Idury, R.M., Sch\u00e4ffer, A.A.: Multiple matching of rectangular patterns. Inf. Comput. 117(1), 78\u201390 (1995)","journal-title":"Inf. Comput."},{"issue":"5","key":"65_CR21","doi-asserted-by":"crossref","first-page":"998","DOI":"10.1137\/S0097539792190157","volume":"25","author":"ZM Kedem","year":"1996","unstructured":"Kedem, Z.M., Landau, G.M., Palem, K.V.: Parallel suffix\u2013prefix-matching algorithm and applications. SIAM J. Comput. 25(5), 998\u20131023 (1996)","journal-title":"SIAM J. Comput."},{"key":"65_CR22","volume-title":"The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 2. Addison Wesley, Redwood (1998)"},{"key":"65_CR23","volume-title":"Elementary Number Theory with Applications","author":"T Koshy","year":"2001","unstructured":"Koshy, T.: Elementary Number Theory with Applications, 2nd edn. Academic Press, New York (2001)","edition":"2"},{"key":"65_CR24","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107341005","volume-title":"Applied Combinatorics on Words (Encyclopedia of Mathematics and Its Applications)","author":"M Lothaire","year":"2005","unstructured":"Lothaire, M.: Applied Combinatorics on Words (Encyclopedia of Mathematics and Its Applications). Cambridge University Press, New York (2005)"},{"issue":"2","key":"65_CR25","first-page":"212","volume":"77","author":"RC Lyndon","year":"1954","unstructured":"Lyndon, R.C.: On Burnside\u2019s problem. Trans. Am. Math. Soc. 77(2), 212\u2013215 (1954)","journal-title":"Trans. Am. Math. Soc."},{"key":"65_CR26","doi-asserted-by":"crossref","unstructured":"Mucha, M.: Lyndon words and short superstrings. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 958\u2013972 (2013)","DOI":"10.1137\/1.9781611973105.69"},{"issue":"3","key":"65_CR27","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1007\/s00453-012-9615-9","volume":"65","author":"S Neuburger","year":"2013","unstructured":"Neuburger, S., Sokol, D.: Succinct 2D dictionary matching. Algorithmica 65(3), 662\u2013684 (2013)","journal-title":"Algorithmica"},{"issue":"3","key":"65_CR28","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.ipl.2009.10.015","volume":"110","author":"E Ohlebusch","year":"2010","unstructured":"Ohlebusch, E., Gog, S.: Efficient algorithms for the all-pairs suffix\u2013prefix problem and the all-pairs substring-prefix problem. Inf. Process. Lett. 110(3), 123\u2013128 (2010)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0065-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0065-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0065-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0065-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:22Z","timestamp":1559087242000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0065-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["65"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0065-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,3]]}}}