{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:07Z","timestamp":1759638067091,"version":"3.41.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_32","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"386-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Universal Reconstruction of a String"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Alatabbi, A., Rahman, M.S., Smyth, W.: Inferring an indeterminate string from a prefix graph. J. of Discrete Algorithms (2014)","DOI":"10.1016\/j.jda.2014.12.006"},{"key":"32_CR2","unstructured":"Bannai, H., Tomohiro, I., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. ArXiv e-prints 1406.0263v6 (2015)"},{"key":"32_CR3","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. 2747, pp. 208\u2013217. Springer, Heidelberg (2003)"},{"key":"32_CR4","unstructured":"Blanchet-Sadri, F., Bodnar, M., Winkle, B.D.: New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings. In: Mayr, E.W., Portier, N. (eds.) Symposium on Theoretical Aspects of Computer Science. LIPIcs, vol. 25, pp. 162\u2013173. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2014)"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.jda.2014.07.002","volume":"28","author":"B Cazaux","year":"2014","unstructured":"Cazaux, B., Rivals, E.: Reverse engineering of compact suffix trees and links: A novel algorithm. J. Discrete Algorithms 28, 9\u201322 (2014)","journal-title":"J. Discrete Algorithms"},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"Christodoulakis, M., Ryan, P.J., Smyth, W.F., Wang, S.: Indeterminate strings, prefix arrays & undirected graphs. ArXiv e-prints 1406.3289 (2014)","DOI":"10.1016\/j.tcs.2015.06.056"},{"key":"32_CR7","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Albers, S., Marion, J.Y. (eds.) Symposium on Theoretical Aspects of Computer Science. LIPIcs, vol. 3, pp. 289\u2013300. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2009)"},{"key":"32_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)"},{"key":"32_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.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 251\u2013259. Springer, Heidelberg (2010)"},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific (2003)","DOI":"10.1142\/4838"},{"issue":"1","key":"32_CR11","first-page":"51","volume":"10","author":"J Duval","year":"2005","unstructured":"Duval, J., Lecroq, T., Lefebvre, A.: Border array on bounded alphabet. Journal of Automata, Languages and Combinatorics 10(1), 51\u201360 (2005)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"02","key":"32_CR12","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1051\/ita:2008030","volume":"43","author":"J Duval","year":"2009","unstructured":"Duval, J., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays and validation of string matching automata. RAIRO-Theor. Inf. Appl. 43(02), 281\u2013297 (2009)","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"32_CR13","first-page":"223","volume":"42","author":"F Franek","year":"2002","unstructured":"Franek, F., Gao, S., Lu, W., Ryan, P., Smyth, W., Sun, Y., Yang, L.: Verifying a border array in linear time. J. on Combinatorial Mathematics and Combinatorial Computing 42, 223\u2013236 (2002)","journal-title":"J. on Combinatorial Mathematics and Combinatorial Computing"},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"ML Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"32_CR15","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00224-013-9522-8","volume":"54","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Je\u017c, A., Je\u017c, P.: Validating the Knuth-Morris-Pratt failure function, fast and online. Theor. Comput. Syst. 54(2), 337\u2013372 (2014)","journal-title":"Theor. Comput. Syst."},{"key":"32_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-642-22300-6_41","volume-title":"Algorithms and Data Structures","author":"J He","year":"2011","unstructured":"He, J., Liang, H., Yang, G.: Reversing longest previous factor tables is hard. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 488\u2013499. Springer, Heidelberg (2011)"},{"key":"32_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-16321-0_13","volume-title":"String Processing and Information Retrieval","author":"I Tomohiro","year":"2010","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Counting and verifying maximal palindromes. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 135\u2013146. Springer, Heidelberg (2010)"},{"issue":"50","key":"32_CR18","doi-asserted-by":"publisher","first-page":"6959","DOI":"10.1016\/j.tcs.2011.09.008","volume":"412","author":"I Tomohiro","year":"2011","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Verifying and enumerating parameterized border arrays. Theor. Comput. Sci. 412(50), 6959\u20136981 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.dam.2013.02.033","volume":"163","author":"I Tomohiro","year":"2014","unstructured":"Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from suffix trees and links on a binary alphabet. Discrete Appl. Math. 163, 316\u2013325 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"32_CR20","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 53(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"32_CR21","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: Fischer, P.C., Zeiger, H.P., Ullman, J.D., Rosenberg, A.L. (eds.) 4th Annual ACM Symposium on Theory of Computing, pp. 125\u2013136. ACM (1972)","DOI":"10.1145\/800152.804905"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. In: Indyk, P. (ed.) Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 532\u2013551. SIAM (2015)","DOI":"10.1137\/1.9781611973730.36"},{"key":"32_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/978-3-319-07566-2_22","volume-title":"Combinatorial Pattern Matching","author":"R Kolpakov","year":"2014","unstructured":"Kolpakov, R., Podolskiy, M., Posypkin, M., Khrapov, N.: Searching of gapped repeats and subrepetitions in a word. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 212\u2013221. Springer, Heidelberg (2014)"},{"key":"32_CR24","doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pp. 596\u2013604. IEEE Computer Society (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"32_CR25","unstructured":"Matsubara, W., Ishino, A., Shinohara, A.: Inferring strings from runs. In: Holub, J., Zd\u00e1rek, J. (eds.) Prague Stringology Conference, pp. 150\u2013160. Czech Technical University (2010)"},{"key":"32_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-28076-4_17","volume-title":"WALCOM: Algorithms and Computation","author":"TM Moosa","year":"2012","unstructured":"Moosa, T.M., Nazeen, S., Rahman, M.S., Reaz, R.: Linear time inference of strings from cover arrays using a binary alphabet. In: Rahman, M.S., Nakano, S. (eds.) WALCOM 2012. LNCS, vol. 7157, pp. 160\u2013172. Springer, Heidelberg (2012)"},{"key":"32_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/978-3-662-44465-8_48","volume-title":"Mathematical Foundations of Computer Science 2014","author":"Y Nakashima","year":"2014","unstructured":"Nakashima, Y., Okabe, T., Tomohiro, I., Inenaga, S., Bannai, H., Takeda, M.: Inferring strings from lyndon factorization. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part II. LNCS, vol. 8635, pp. 565\u2013576. Springer, Heidelberg (2014)"},{"key":"32_CR28","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jda.2015.01.005","volume":"32","author":"T Starikovskaya","year":"2015","unstructured":"Starikovskaya, T., Vildh\u00f8j, H.W.: A suffix tree or not a suffix tree? J. Discrete Algorithms 32, 14\u201314 (2015)","journal-title":"J. Discrete Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T18:50:27Z","timestamp":1748544627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}