{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:41Z","timestamp":1759637741280},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642222993"},{"type":"electronic","value":"9783642223006"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22300-6_41","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:41:31Z","timestamp":1312893691000},"page":"488-499","source":"Crossref","is-referenced-by-count":3,"title":["Reversing Longest Previous Factor Tables is Hard"],"prefix":"10.1007","author":[{"given":"Jing","family":"He","sequence":"first","affiliation":[]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[]},{"given":"Guang","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"41_CR1","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1137\/0215007","volume":"15","author":"A. Apostolico","year":"1986","unstructured":"Apostolico, A., Giancarlo, R.: The Boyer-Moore-Galil string searching strategies revisited. SIAM J. Comput.\u00a015(1), 98\u2013105 (1986)","journal-title":"SIAM J. Comput."},{"key":"41_CR2","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":"10","key":"41_CR3","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commin. ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Commin. ACM"},{"key":"41_CR4","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: STACS 2009, Freiburg, pp. 289\u2013300 (2009)"},{"issue":"1","key":"41_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0304-3975(86)90041-1","volume":"45","author":"M. Crochemore","year":"1986","unstructured":"Crochemore, M.: Transducers and repetitions. Theoret. Comput. Sci.\u00a045(1), 63\u201386 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"41_CR6","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)"},{"issue":"2","key":"41_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","volume":"106","author":"M. Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Computing Longest Previous Factor in linear time and applications. Inf. Process. Lett.\u00a0106(2), 75\u201380 (2008)","journal-title":"Inf. Process. Lett."},{"key":"41_CR8","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.\u00a06129, pp. 251\u2013259. Springer, Heidelberg (2010)"},{"issue":"4","key":"41_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0020-0190(97)00107-5","volume":"63","author":"M. Crochemore","year":"1997","unstructured":"Crochemore, M., Lecroq, T.: Tight bounds on the complexity of the Apostolico-Giancarlo algorithm. Inf. Process. Lett.\u00a063(4), 195\u2013203 (1997)","journal-title":"Inf. Process. Lett."},{"key":"41_CR10","unstructured":"Duval, J.-P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of border arrays. In: Proceedings of 11th Mons Days of Theoretical Computer Science, Rennes, France, pp. 179\u2013189 (2006)"},{"key":"41_CR11","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. Combinatorial Math. and Combinatorial Computing\u00a042, 223\u2013236 (2002)","journal-title":"J. Combinatorial Math. and Combinatorial Computing"},{"issue":"6","key":"41_CR12","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1142\/S0129054106004418","volume":"17","author":"F. Franek","year":"2006","unstructured":"Franek, F., Smyth, W.F.: Reconstructing a Suffix Array. International Journal of Foundations of Computer Science\u00a017(6), 1281\u20131295 (2006)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"41_CR13","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., Je\u017c, A., Je\u017c, \u0141.: Validating the Knuth-Morris-Pratt failure function, fast and online. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol.\u00a06072, pp. 132\u2013143. Springer, Heidelberg (2010)"},{"key":"41_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees and sequences: computer science and computational biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on strings, trees and sequences: computer science and computational biology. Cambridge University Press, Cambridge (1997)"},{"key":"41_CR15","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.) CPM 2010. LNCS, vol.\u00a06129, pp. 238\u2013250. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-13509-5_22"},{"issue":"1","key":"41_CR16","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(1), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"41_CR17","first-page":"596","volume-title":"FOCS 1999","author":"R. Kolpakov","year":"1999","unstructured":"Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: FOCS 1999, pp. 596\u2013604. IEEE Computer Society Press, New York (1999)"},{"key":"41_CR18","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0166-218X(89)90051-6","volume":"25","author":"M.G. Main","year":"1989","unstructured":"Main, M.G.: Detecting leftmost maximal periodicities. Discrete Applied Math.\u00a025, 145\u2013153 (1989)","journal-title":"Discrete Applied Math."},{"issue":"5","key":"41_CR19","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line search. SIAM J. Comput.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"41_CR20","unstructured":"Matsubara, W., Ishino, A., Shinohara, A.: Inferring strings from runs. In: Prague Stringology Conference 2010, pp. 150\u2013160 (2010)"},{"key":"41_CR21","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A Universal algorithm for sequential data compression. IEEE Trans. Inform. Theory\u00a023, 337\u2013342 (1977)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"41_CR22","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory\u00a024, 530\u2013536 (1978)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22300-6_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T22:54:02Z","timestamp":1560466442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22300-6_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642222993","9783642223006"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22300-6_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}