{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:03:27Z","timestamp":1725455007878},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642341083"},{"type":"electronic","value":"9783642341090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34109-0_1","type":"book-chapter","created":{"date-parts":[[2012,9,13]],"date-time":"2012-09-13T11:14:53Z","timestamp":1347534893000},"page":"1-15","source":"Crossref","is-referenced-by-count":2,"title":["Approximate Period Detection and Correction"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1221\u20131229 (2006)","DOI":"10.1145\/1109557.1109692"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. Journal of Algorithms\u00a037, 247\u2013266 (2000); Preliminary version appeared at FOCS 1997","journal-title":"Journal of Algorithms"},{"issue":"1","key":"1_CR3","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1137\/S0097539795298321","volume":"27","author":"A. Amir","year":"1998","unstructured":"Amir, A., Benson, G.: Two-dimensional periodicity and its application. SIAM J. Comp.\u00a027(1), 90\u2013106 (1998)","journal-title":"SIAM J. Comp."},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-17517-6_5","volume-title":"Algorithms and Computation","author":"A. Amir","year":"2010","unstructured":"Amir, A., Eisenberg, E., Levy, A.: Approximate Periodicity. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 25\u201336. Springer, Heidelberg (2010)"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/978-3-642-25591-5_73","volume-title":"Algorithms and Computation","author":"A. Amir","year":"2011","unstructured":"Amir, A., Eisenberg, E., Levy, A., Lewenstein, N.: Closest Periodic Vectors in L\n                p Spaces. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 714\u2013723. Springer, Heidelberg (2011)"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-642-14165-2_5","volume-title":"Automata, Languages and Programming","author":"A. Amir","year":"2010","unstructured":"Amir, A., Eisenberg, E., Levy, A., Porat, E., Shapira, N.: Cycle Detection and Correction. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 43\u201354. Springer, Heidelberg (2010)"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-540-75520-3_11","volume-title":"Algorithms \u2013 ESA 2007","author":"A. Amir","year":"2007","unstructured":"Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the Cost of Interchange Rearrangement in Strings. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 99\u2013110. Springer, Heidelberg (2007)"},{"issue":"9","key":"1_CR8","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1016\/j.dam.2006.11.017","volume":"156","author":"A. Apostolico","year":"2008","unstructured":"Apostolico, A., Giancarlo, R.: Periodicity and repetitions in parameterized strings. Discrete Appl. Math.\u00a0156(9), 1389\u20131398 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"1_CR9","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/BF01955046","volume":"15","author":"A. Apostolico","year":"1996","unstructured":"Apostolico, A., Preparata, F.P.: Data structures and algorithms for the string statistics problem. Algorithmica\u00a015(5), 481\u2013494 (1996)","journal-title":"Algorithmica"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. on Discrete Mathematics\u00a011, 221\u2013240 (1998)","journal-title":"SIAM J. on Discrete Mathematics"},{"issue":"3","key":"1_CR11","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1089\/cmb.1997.4.351","volume":"4","author":"G. Benson","year":"1997","unstructured":"Benson, G.: Sequence alignment with tandem duplication. J. Computational Biology\u00a04(3), 351\u2013368 (1997)","journal-title":"J. Computational Biology"},{"key":"1_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/3-540-61258-0_14","volume-title":"Combinatorial Pattern Matching","author":"P. Berman","year":"1996","unstructured":"Berman, P., Hannenhalli, S.: Fast Sorting by Reversal. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 168\u2013185. Springer, Heidelberg (1996)"},{"key":"1_CR13","first-page":"527","volume":"34","author":"A. Cayley","year":"1849","unstructured":"Cayley, A.: Note on the theory of permutations. Philosophical Magazine (34), 527\u2013529 (1849)","journal-title":"Philosophical Magazine"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","volume":"60","author":"D.A. Christie","year":"1996","unstructured":"Christie, D.A.: Sorting by block-interchanges. Information Processing Letters\u00a060, 165\u2013169 (1996)","journal-title":"Information Processing Letters"},{"issue":"5","key":"1_CR15","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. Information Processing Letters\u00a012(5), 244\u2013250 (1981)","journal-title":"Information Processing Letters"},{"key":"1_CR16","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol.\u00a07, pp. 113\u2013125 (1974)"},{"issue":"4","key":"1_CR17","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 mismatches. SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"issue":"5","key":"1_CR18","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1137\/S0097539792241941","volume":"25","author":"Z. Galil","year":"1996","unstructured":"Galil, Z., Park, K.: Alphabet-independent two-dimensional witness computation. SIAM J. Comp.\u00a025(5), 907\u2013935 (1996)","journal-title":"SIAM J. Comp."},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Gfeller, B.: Finding longest approximate periodic patterns. In: WADS (2011)","DOI":"10.1007\/978-3-642-22300-6_39"},{"key":"1_CR20","first-page":"338","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor. Computer and System Science\u00a013, 338\u2013355 (1984)","journal-title":"Computer and System Science"},{"key":"1_CR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple Linear Work Suffix Array Construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 943\u2013955. Springer, Heidelberg (2003)"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G.H., Arimura, H., Arikawa, S., Park, K.: Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"issue":"13","key":"1_CR23","doi-asserted-by":"publisher","first-page":"3672","DOI":"10.1093\/nar\/gkg617","volume":"31","author":"R.M. Kolpakov","year":"2003","unstructured":"Kolpakov, R.M., Bana, G., Kucherov, G.: mreps: efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Research\u00a031(13), 3672\u20133678 (2003)","journal-title":"Nucleic Acids Research"},{"issue":"303","key":"1_CR24","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(02)00448-6","volume":"1","author":"R.M. Kolpakov","year":"2003","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding approximate repetitions under hamming distance. Theoretical Computer Science\u00a01(303), 135\u2013156 (2003)","journal-title":"Theoretical Computer Science"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"key":"1_CR26","unstructured":"Lothaire, M.: Combinatorics on words. Addison-Wesley, Reading (1983)"},{"key":"1_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BFb0029807","volume-title":"Combinatorial Pattern Matching","author":"M. R\u00e9gnier","year":"1993","unstructured":"R\u00e9gnier, M., Rostami, L.: A Unifying Look at d-dimensional Periodicities and Space Coverings. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol.\u00a0684, pp. 215\u2013227. Springer, Heidelberg (1993)"},{"issue":"1","key":"1_CR28","first-page":"16","volume":"29","author":"J.S. Sim","year":"2001","unstructured":"Sim, J.S., Park, K., Kim, S., Lee, J.: Finding approximate covers of strings. J. Korea Information Science Society\u00a029(1), 16\u201321 (2001)","journal-title":"J. Korea Information Science Society"},{"issue":"2","key":"1_CR29","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1093\/bioinformatics\/btl309","volume":"23","author":"D. Sokol","year":"2007","unstructured":"Sokol, D., Benson, G., Tojeira, J.: Tandem repeats over the edit distance. Bioinformatics\u00a023(2), 30\u201335 (2007)","journal-title":"Bioinformatics"},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14 IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34109-0_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:45:03Z","timestamp":1620132303000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34109-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642341083","9783642341090"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34109-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}