{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T21:24:55Z","timestamp":1791581095116,"version":"4.3.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,6]],"date-time":"2013-12-06T00:00:00Z","timestamp":1386288000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00224-013-9522-8","type":"journal-article","created":{"date-parts":[[2013,12,5]],"date-time":"2013-12-05T01:33:23Z","timestamp":1386207203000},"page":"337-372","source":"Crossref","is-referenced-by-count":20,"title":["Validating the Knuth-Morris-Pratt Failure Function, Fast and Online"],"prefix":"10.1007","volume":"54","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Artur","family":"Je\u017c","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,12,6]]},"reference":[{"issue":"1","key":"9522_CR1","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1006\/jagm.1998.0948","volume":"29","author":"D. Breslauer","year":"1998","unstructured":"Breslauer, D., Colussi, L., Toniolo, L.: On the comparison complexity of the string prefix-matching problem. J. Algorithms 29(1), 18\u201367 (1998)","journal-title":"J. Algorithms"},{"key":"9522_CR2","first-page":"289","volume-title":"Proceedings of 26th STACS","author":"J. Cl\u00e9ment","year":"2009","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proceedings of 26th STACS, pp. 289\u2013300 (2009). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1825"},{"key":"9522_CR3","first-page":"235","volume-title":"Proceedings of SODA \u201999","author":"R. Cole","year":"1999","unstructured":"Cole, R., Hariharan, R.: Dynamic lca queries on trees. In: Proceedings of SODA \u201999, pp. 235\u2013244. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"9522_CR4","doi-asserted-by":"crossref","DOI":"10.1142\/4838","volume-title":"Jewels of Stringology","author":"M. Crochemore","year":"2002","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific Publishing Company, Singapore (2002)"},{"key":"9522_CR5","doi-asserted-by":"crossref","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":"9522_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-642-13509-5_23","volume-title":"CPM 2010","author":"M. Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C., Pissis, S., Tischler, G.: Cover array string reconstruction. In: CPM 2010. Lecture Notes in Computer Science, vol. 6129, pp. 251\u2013259. Springer, Berlin (2010)"},{"issue":"4","key":"9522_CR7","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A.R., Mehlhorn, K., auf der Heide, F.M., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: upper and lower bounds. SIAM J. Comput. 23(4), 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"key":"9522_CR8","volume-title":"Conference in Honor of Donald E. Knuth","author":"J.P. Duval","year":"2007","unstructured":"Duval, J.P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of Knuth\u2013Morris\u2013Pratt arrays. In: Conference in Honor of Donald E. Knuth (2007)"},{"issue":"2","key":"9522_CR9","doi-asserted-by":"crossref","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 Theor. Inform. Appl. 43(2), 281\u2013297 (2009). doi: 10.1051\/ita:2008030","journal-title":"RAIRO Theor. Inform. Appl."},{"key":"9522_CR10","first-page":"137","volume-title":"Proceedings of FOCS \u201997","author":"M. Farach","year":"1997","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: Proceedings of FOCS \u201997, pp. 137\u2013143. IEEE Computer Society, Washington (1997)"},{"key":"9522_CR11","first-page":"223","volume":"42","author":"F. Fran\u011bk","year":"2002","unstructured":"Fran\u011bk, 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. Comb. Comput. 42, 223\u2013236 (2002)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"9522_CR12","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. 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). doi: 10.1016\/S0022-0000(05)80064-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9522_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(93)90231-W","volume":"47","author":"C. Hancart","year":"1993","unstructured":"Hancart, C.: On Simon\u2019s string searching algorithm. Inf. Process. Lett. 47(2), 95\u201399 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9522_CR14","first-page":"422","volume-title":"Proc. of the 3rd LATA","author":"T. I","year":"2009","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays for a binary alphabet. In: Proc. of the 3rd LATA, pp. 422\u2013433 (2009). doi: 10.1007\/978-3-642-00982-2_36"},{"issue":"50","key":"9522_CR15","doi-asserted-by":"crossref","first-page":"6959","DOI":"10.1016\/j.tcs.2011.09.008","volume":"412","author":"T. I","year":"2011","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Verifying and enumerating parameterized border arrays. Theor. Comput. Sci. 412(50), 6959\u20136981 (2011). doi: 10.1016\/j.tcs.2011.09.008","journal-title":"Theor. Comput. Sci."},{"key":"9522_CR16","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1145\/800152.804905","volume-title":"STOC \u201972: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M., Miller, R.E., Rosenberg, A.L.: Rapid identification of repeated patterns in strings, trees and arrays. In: STOC \u201972: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing, pp. 125\u2013136. ACM, New York (1972). doi: 10.1145\/800152.804905"},{"issue":"2","key":"9522_CR17","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H. Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"9522_CR18","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF01117471","volume":"1","author":"Y. Matiyasevich","year":"1973","unstructured":"Matiyasevich, Y.: Real-time recognition of the inclusion relation. J. Sov. Math. 1, 64\u201370 (1973). Published (in Russian) in Zap. Nauc\u0306. Semin. POMI, 20, 104\u2013114 (1971)","journal-title":"J. Sov. Math."},{"issue":"2","key":"9522_CR19","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976). doi: 10.1145\/321941.321946","journal-title":"J. ACM"},{"issue":"1","key":"9522_CR20","doi-asserted-by":"crossref","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 23(1), 1\u201313 (1999). http:\/\/link.springer.de\/link\/service\/journals\/00453\/bibs\/23n1p1.html","journal-title":"Algorithmica"},{"key":"9522_CR21","unstructured":"Morris, J.H. Jr., Pratt, V.R.: A linear pattern-matching algorithm. Tech. Rep. 40, University of California, Berkeley (1970)"},{"issue":"2","key":"9522_CR22","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004). doi: 10.1016\/j.jalgor.2003.12.002","journal-title":"J. Algorithms"},{"key":"9522_CR23","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-58131-6_61","volume-title":"Results and Trends in Theoretical Computer Science","author":"I. Simon","year":"1994","unstructured":"Simon, I.: String matching algorithms and automata. In: Results and Trends in Theoretical Computer Science. LNCS, vol. 812, pp. 386\u2013395. Springer, Berlin (1994)"},{"issue":"3","key":"9522_CR24","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995). doi: 10.1007\/BF01206331","journal-title":"Algorithmica"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-013-9522-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9522-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-013-9522-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T19:12:49Z","timestamp":1551208369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-013-9522-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9522"],"URL":"https:\/\/doi.org\/10.1007\/s00224-013-9522-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,6]]}}}