{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:17Z","timestamp":1770994037327,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642163203","type":"print"},{"value":"9783642163210","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16321-0_13","type":"book-chapter","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T10:51:32Z","timestamp":1286275892000},"page":"135-146","source":"Crossref","is-referenced-by-count":8,"title":["Counting and Verifying Maximal Palindromes"],"prefix":"10.1007","author":[{"given":"Tomohiro","family":"I","sequence":"first","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-3975(01)00212-2","volume":"292","author":"J.P. Allouche","year":"2003","unstructured":"Allouche, J.P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoretical Computer Science\u00a0292(1), 9\u201331 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.disc.2009.08.002","volume":"310","author":"M.C. Anisiu","year":"2010","unstructured":"Anisiu, M.C., Anisiu, V., K\u00e1sa, Z.: Total palindrome complexity of finite words. Discrete Mathematics\u00a0310(1), 109\u2013114 (2010)","journal-title":"Discrete Mathematics"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/3-540-55719-9_82","volume-title":"Automata, Languages and Programming","author":"A. Apostolico","year":"1992","unstructured":"Apostolico, A., Breslauer, D., Galil, Z.: Optimal parallel algorithms for periods, palindromes and squares. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 296\u2013307. Springer, Heidelberg (1992)"},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0304-3975(94)00083-U","volume":"141","author":"A. Apostolico","year":"1995","unstructured":"Apostolico, A., Breslauer, D., Galil, Z.: Parallel detection of all palindromes in a string. Theoretical Computer Science\u00a0141, 163\u2013173 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR5","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1006\/jcss.1996.0003","volume":"52","author":"B.S. Baker","year":"1996","unstructured":"Baker, B.S.: Parameterized pattern matching: Algorithms and applications. Journal of Computer and System Sciences\u00a052(1), 28\u201342 (1996)","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-45138-9_15","volume-title":"Mathematical Foundations of Computer Science 2003","author":"H. Bannai","year":"2003","unstructured":"Bannai, H., Inenaga, S., Shinohara, A., Takeda, M.: Inferring strings from graphs and arrays. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 208\u2013217. Springer, Heidelberg (2003)"},{"issue":"4","key":"13_CR7","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"},{"key":"13_CR8","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proc. STACS 2009, pp. 289\u2013300 (2009)"},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-13509-5_23","volume-title":"Combinatorial Pattern Matching","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C., Pissis, S., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a06129, pp. 251\u2013259. Springer, Heidelberg (2010)"},{"issue":"1-3","key":"13_CR10","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.tcs.2007.09.015","volume":"396","author":"J.D. Currie","year":"2008","unstructured":"Currie, J.D.: Palindrome positions in ternary square-free words. Theoretical Computer Science\u00a0396(1-3), 254\u2013257 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"13_CR11","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0020-0190(95)00080-V","volume":"55","author":"X. Droubay","year":"1995","unstructured":"Droubay, X.: Palindromes in the Fibonacci word. Information Processing Letters\u00a055(4), 217\u2013221 (1995)","journal-title":"Information Processing Letters"},{"issue":"1-2","key":"13_CR12","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(97)00188-6","volume":"223","author":"X. Droubay","year":"1999","unstructured":"Droubay, X., Pirillo, G.: Palindromes and Sturmian words. Theoretical Computer Science\u00a0223(1-2), 73\u201385 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"13_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1051\/ita:2008030","volume":"43","author":"J.P. Duval","year":"2009","unstructured":"Duval, J.P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO - Theoretical Informatics and Applications\u00a043(2), 281\u2013297 (2009)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"issue":"1","key":"13_CR14","first-page":"51","volume":"10","author":"J.P. Duval","year":"2005","unstructured":"Duval, J.P., Lecroq, T., Lefevre, A.: Border array on bounded alphabet. Journal of Automata, Languages and Combinatorics\u00a010(1), 51\u201360 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1051\/ita:2002012","volume":"36","author":"J.P. Duval","year":"2002","unstructured":"Duval, J.P., Lefebvre, A.: Words over an ordered alphabet and suffix permutations. Theoretical Informatics and Applications\u00a036, 249\u2013259 (2002)","journal-title":"Theoretical Informatics and Applications"},{"key":"13_CR16","first-page":"223","volume":"42","author":"F. Franek","year":"2002","unstructured":"Franek, F., Gao, S., Lu, W., Ryan, P.J., Smyth, W.F., Sun, Y., Yang, L.: Verifying a border array in linear time. J. Comb. Math. and Comb. Comp.\u00a042, 223\u2013236 (2002)","journal-title":"J. Comb. Math. and Comb. Comp."},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Algorithm Theory - SWAT \u201996","author":"L. Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol.\u00a01097, pp. 392\u2013403. Springer, Heidelberg (1996)"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-13182-0_13","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. Gawrychowski","year":"2010","unstructured":"Gawrychowski, P., Jez, A., Jez, L.: Validating the Knuth-Morris-Pratt failure function, fast and online. In: Ablayev, F., Mayr, E.W. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a06072, pp. 132\u2013143. Springer, Heidelberg (2010)"},{"issue":"1","key":"13_CR19","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2005.09.075","volume":"352","author":"A. Glen","year":"2006","unstructured":"Glen, A.: Occurrences of palindromes in characteristic Sturmian words. Theoretical Computer Science\u00a0352(1), 31\u201346 (2006)","journal-title":"Theoretical Computer Science"},{"key":"13_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, New York (1997)"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1007\/978-3-642-10631-6_109","volume-title":"Algorithms and Computation","author":"P.H. Hsu","year":"2009","unstructured":"Hsu, P.H., Chen, K.Y., Chao, K.M.: Finding all approximate gapped palindromes. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 1084\u20131093. Springer, Heidelberg (2009)"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays for a binary alphabet. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 422\u2013433. Springer, Heidelberg (2009)","DOI":"10.1007\/978-3-642-00982-2_36"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Verifying a parameterized border array in O(n 1.5) time. In: Amir, A., Parida, L. (eds.) Combinatorial Pattern Matching. LNCS, vol.\u00a06129, pp. 238\u2013250. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-13509-5_22"},{"issue":"2","key":"13_CR24","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"51","key":"13_CR25","doi-asserted-by":"publisher","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","volume":"410","author":"R. Kolpakov","year":"2009","unstructured":"Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theoretical Computer Science\u00a0410(51), 5365\u20135373 (2009)","journal-title":"Theoretical Computer Science"},{"key":"13_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/11505877_18","volume-title":"Developments in Language Theory","author":"A. Luca de","year":"2005","unstructured":"de Luca, A., Luca, A.D.: Palindromes in Sturmian words. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol.\u00a03572, pp. 199\u2013208. Springer, Heidelberg (2005)"},{"issue":"3","key":"13_CR27","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. Journal of the ACM\u00a022(3), 346\u2013351 (1975)","journal-title":"Journal of the ACM"},{"issue":"8\u201310","key":"13_CR28","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. Theoretical Computer Science\u00a0410(8\u201310), 900\u2013913 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009247","volume":"23","author":"D. Moore","year":"1999","unstructured":"Moore, D., Smyth, W.F., Miller, D.: Counting distinct strings. Algorithmica\u00a023(1), 1\u201313 (1999)","journal-title":"Algorithmica"},{"issue":"11","key":"13_CR30","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/S0031-3203(01)00179-0","volume":"35","author":"A.H.L. Porto","year":"2002","unstructured":"Porto, A.H.L., Barbosa, V.C.: Finding approximate palindromes in strings. Pattern Recognition\u00a035(11), 2581\u20132591 (2002)","journal-title":"Pattern Recognition"},{"issue":"2-1","key":"13_CR31","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2008.01.011","volume":"395","author":"K.B. Sch\u00fcrmann","year":"2008","unstructured":"Sch\u00fcrmann, K.B., Stoye, J.: Counting suffix arrays and strings. Theoretical Computer Science\u00a0395(2-1), 220\u2013234 (2008)","journal-title":"Theoretical Computer Science"}],"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-16321-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T03:13:16Z","timestamp":1559704396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16321-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163203","9783642163210"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16321-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}