{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T22:10:05Z","timestamp":1748815805704,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662495285"},{"type":"electronic","value":"9783662495292"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49529-2_5","type":"book-chapter","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T08:09:41Z","timestamp":1458547781000},"page":"55-67","source":"Crossref","is-referenced-by-count":1,"title":["Period Recovery over the Hamming and Edit Distances"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[]},{"given":"Mika","family":"Amit","sequence":"additional","affiliation":[]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,22]]},"reference":[{"issue":"1","key":"5_CR1","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2390176.2390189","volume":"9","author":"A Amir","year":"2012","unstructured":"Amir, A., Eisenberg, E., Levy, A., Porat, E., Shapira, N.: Cycle detection and correction. ACM Trans. Algorithms 9(1), 13:1\u201313:20 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-642-38905-4_4","volume-title":"Combinatorial Pattern Matching","author":"M Amit","year":"2013","unstructured":"Amit, M., Crochemore, M., Landau, G.M.: Locating all maximal approximate runs in a string. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 13\u201327. Springer, Heidelberg (2013)"},{"key":"5_CR3","unstructured":"Bannai, H.., Inenaga, T.I.S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. CoRR, abs\/1406.0263v4 (2014)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1007\/3-540-45465-9_62","volume-title":"Automata, Languages and Programming","author":"GS Brodal","year":"2002","unstructured":"Brodal, G.S., Lyngs\u00f8, R.B., \u00d6stlin, A., Pedersen, C.N.S.: Solving the string statistics problem in time $${{\\cal O}}(n \\log n)$$ O ( n log n ) . In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 728\u2013739. Springer, Heidelberg (2002)"},{"issue":"3","key":"5_CR5","first-page":"22","volume":"9","author":"TM Chan","year":"2013","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word ram. ACM Trans. Algorithms (TALG) 9(3), 22 (2013)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"5_CR6","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17(3), 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"5_CR7","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M Crochemore","year":"1981","unstructured":"Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett. 12(5), 244\u2013250 (1981)","journal-title":"Inf. Process. Lett."},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings, 392 p. Cambridge University Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511546853"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-16321-0_27","volume-title":"String Processing and Information Retrieval","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Extracting powers and periods in a string from its runs structure. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 258\u2013269. Springer, Heidelberg (2010)"},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16, 109\u2013114 (1965)","journal-title":"Proc. Am. Math. Soc."},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0020-0190(93)90245-5","volume":"45","author":"VA Fischetti","year":"1993","unstructured":"Fischetti, V.A., Landau, G.M., Sellers, P.H., Schmidt, J.P.: Identifying periodic occurences of a template with applications to protein structure. Inf. Process. Lett. 45(1), 11\u201318 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"5_CR12","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with $$k$$ k mismatches. SIGACT News 17(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"issue":"4","key":"5_CR13","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1016\/j.jcss.2004.03.004","volume":"69","author":"D Gusfield","year":"2004","unstructured":"Gusfield, D., Stoye, J.: Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci. 69(4), 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20132","key":"5_CR14","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0304-3975(96)00141-7","volume":"172","author":"CS Iliopoulos","year":"1997","unstructured":"Iliopoulos, C.S., Moore, D., Smyth, W.F.: A characterization of the squares in a Fibonacci string. Theor. Comput. Sci. 172(1\u20132), 281\u2013291 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patterns in strings, trees, and arrays. In: STOC: ACM Symposium on Theory of Computing (STOC) (1972)","DOI":"10.1145\/800152.804905"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 596\u2013604 (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"issue":"303","key":"5_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(02)00448-6","volume":"1","author":"RM Kolpakov","year":"2003","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding approximate repetitions under Hamming distance. Theor. Comput. Sci 1(303), 135\u2013156 (2003)","journal-title":"Theor. Comput. Sci"},{"issue":"1","key":"5_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"GM Landau","year":"2001","unstructured":"Landau, G.M., Schmidt, J.P., Sokol, D.: An algorithm for approximate tandem repeats. J. Comput. Biol. 8(1), 1\u201318 (2001)","journal-title":"J. Comput. Biol."},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"GM Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms 10(2), 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"key":"5_CR20","doi-asserted-by":"publisher","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":"5_CR21","first-page":"202","volume":"77","author":"RC Lyndon","year":"1954","unstructured":"Lyndon, R.C.: On Burnside\u2019s problem. Trans. Am. Math. Soc. 77(2), 202\u2013215 (1954)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"5_CR22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF02458834","volume":"51","author":"EW Myers","year":"1989","unstructured":"Myers, E.W., Miller, W.: Approximate matching of regular expressions. Bull. Math. Biol. 51(1), 5\u201337 (1989)","journal-title":"Bull. Math. Biol."},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/3-540-48452-3_10","volume-title":"Combinatorial Pattern Matching","author":"JS Sim","year":"1999","unstructured":"Sim, J.S., Iliopoulos, C.S., Park, K., Smyth, W.F.: Approximate periods of strings. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol. 1645, pp. 123\u2013133. Springer, Heidelberg (1999)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2016: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49529-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T21:29:16Z","timestamp":1748813356000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49529-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662495285","9783662495292"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49529-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}