{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:42:21Z","timestamp":1743046941962,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642312649"},{"type":"electronic","value":"9783642312656"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_24","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"293-305","source":"Crossref","is-referenced-by-count":4,"title":["Time-Space Trade-Offs for Longest Common Extensions"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[]},{"given":"Hjalte Wedel","family":"Vildh\u00f8j","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM\u00a018 (1975)","DOI":"10.1145\/360825.360855"},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-3975(01)00212-2","volume":"292","author":"J. Allouche","year":"2003","unstructured":"Allouche, J., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoret. Comput. Sci.\u00a0292(1), 9\u201331 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A. Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms\u00a050(2), 257\u2013275 (2004)","journal-title":"J. Algorithms"},{"issue":"4","key":"24_CR4","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/BF01294132","volume":"14","author":"D. Breslauer","year":"1995","unstructured":"Breslauer, D., Galil, Z.: Finding all periods and initial palindromes of a string in parallel. Algorithmica\u00a014(4), 355\u2013366 (1995)","journal-title":"Algorithmica"},{"issue":"1-2","key":"24_CR5","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0020-0190(00)00080-6","volume":"75","author":"C.J. Colbourn","year":"2000","unstructured":"Colbourn, C.J., Ling, A.C.: Quorums from difference covers. Inf. Process. Lett.\u00a075(1-2), 9\u201312 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"24_CR6","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1137\/S0097539700370527","volume":"31","author":"R. Cole","year":"2002","unstructured":"Cole, R., Hariharan, R.: Approximate String Matching: A Simpler Faster Algorithm. SIAM J. Comput.\u00a031(6), 1761\u20131782 (2002)","journal-title":"SIAM J. Comput."},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BFb0032018","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"1990","unstructured":"Dietzfelbinger, M., Meyer auf der Heide, F.: A New Universal Class of Hash Functions and Dynamic Hashing in Real Time. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol.\u00a0443, pp. 6\u201319. Springer, Heidelberg (1990)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/11780441_5","volume-title":"Combinatorial Pattern Matching","author":"J. Fischer","year":"2006","unstructured":"Fischer, J., Heun, V.: Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 36\u201348. Springer, Heidelberg (2006)"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"24_CR10","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.\u00a069, 525\u2013546 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2005.01.006","volume":"339","author":"L. G\u0105sieniec","year":"2005","unstructured":"G\u0105sieniec, L., Kolpakov, R., Potapov, I.: Space efficient search for maximal repetitions. Theoret. Comput. Sci.\u00a0339(1), 35\u201348 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"24_CR13","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.jda.2010.08.004","volume":"8","author":"L. Ilie","year":"2010","unstructured":"Ilie, L., Navarro, G., Tinta, L.: The longest common extension problem revisited and applications to approximate string searching. J. of Discrete Algorithms\u00a08, 418\u2013428 (2010)","journal-title":"J. of Discrete Algorithms"},{"issue":"2","key":"24_CR14","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01182773","volume":"11","author":"J. Jeuring","year":"1994","unstructured":"Jeuring, J.: The Derivation of On-Line Algorithms, with an Application to Finding Palindromes. Algorithmica\u00a011(2), 146\u2013184 (1994)","journal-title":"Algorithmica"},{"issue":"6","key":"24_CR15","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J. K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM\u00a053(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"issue":"2","key":"24_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev.\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-540-69068-9_5","volume-title":"Combinatorial Pattern Matching","author":"R. Kolpakov","year":"2008","unstructured":"Kolpakov, R., Kucherov, G.: Searching for Gapped Palindromes. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 18\u201330. Springer, Heidelberg (2008)"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"G.M. Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput.\u00a027(2), 557\u2013582 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"24_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652701300099038","volume":"8","author":"G.M. Landau","year":"2001","unstructured":"Landau, G.M., Schmidt, J.P.: An Algorithm for Approximate Tandem Repeats. J. Comput. Biol.\u00a08(1), 1\u201318 (2001)","journal-title":"J. Comput. Biol."},{"key":"24_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast Parallel and Serial Approximate String Matching. J. Algorithms\u00a010, 157\u2013169 (1989)","journal-title":"J. Algorithms"},{"issue":"3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10142-007-0047-6","volume":"7","author":"L. Lu","year":"2007","unstructured":"Lu, L., Jia, H., Dr\u00f6ge, P., Li, J.: The human genome-wide distribution of DNA palindromes. Funct. Integr. Genomics\u00a07(3), 221\u2013227 (2007)","journal-title":"Funct. Integr. Genomics"},{"issue":"3","key":"24_CR22","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"M.G. Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An O (n log n) algorithm for finding all repetitions in a string. J. Algorithms\u00a05(3), 422\u2013432 (1984)","journal-title":"J. Algorithms"},{"issue":"3","key":"24_CR23","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"G. Manacher","year":"1975","unstructured":"Manacher, G.: A New Linear-Time \u201cOn-Line\u201d Algorithm for Finding the Smallest Initial Palindrome of a String. J. ACM\u00a022(3), 346\u2013351 (1975)","journal-title":"J. ACM"},{"issue":"8-10","key":"24_CR24","doi-asserted-by":"publisher","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W. Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theoret. Comput. Sci.\u00a0410(8-10), 900\u2013913 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"24_CR25","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01840446","volume":"1","author":"E.W. Myers","year":"1986","unstructured":"Myers, E.W.: An O(ND) difference algorithm and its variations. Algorithmica\u00a01(2), 251\u2013266 (1986)","journal-title":"Algorithmica"},{"key":"24_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-540-92182-0_14","volume-title":"Algorithms and Computation","author":"S.J. Puglisi","year":"2008","unstructured":"Puglisi, S.J., Turpin, A.: Space-Time Tradeoffs for Longest-Common-Prefix Array Computation. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 124\u2013135. Springer, Heidelberg (2008)"},{"key":"24_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1328911.1328912","volume":"4","author":"M. Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Uniform deterministic dictionaries. ACM Trans. Algorithms\u00a04, 1\u201323 (2008)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,23]],"date-time":"2023-01-23T22:53:45Z","timestamp":1674514425000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}