{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:38:41Z","timestamp":1725557921895},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642131813"},{"type":"electronic","value":"9783642131820"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13182-0_13","type":"book-chapter","created":{"date-parts":[[2010,6,12]],"date-time":"2010-06-12T10:55:17Z","timestamp":1276340117000},"page":"132-143","source":"Crossref","is-referenced-by-count":3,"title":["Validating the Knuth-Morris-Pratt Failure Function, Fast and Online"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"given":"Artur","family":"Je\u017c","sequence":"additional","affiliation":[]},{"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","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\u00a029(1), 18\u201367 (1998)","journal-title":"J. Algorithms"},{"key":"13_CR2","unstructured":"Cl\u00e9ment, J., Crochemore, M., Rindone, G.: Reverse engineering prefix tables. In: Proceedings of 26th STACS, pp. 289\u2013300 (2009)"},{"key":"13_CR3","unstructured":"Cole, R., Hariharan, R.: Dynamic lca queries on trees. In: Proceedings of SODA \u201999, Philadelphia, PA, USA, pp. 235\u2013244. Society for Industrial and Applied Mathematics (1999)"},{"key":"13_CR4","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":"13_CR5","doi-asserted-by":"publisher","DOI":"10.1142\/9789812778222","volume-title":"Jewels of Stringology","author":"M. Crochemore","year":"2002","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific Publishing Company, Singapore (2002)"},{"issue":"4","key":"13_CR6","doi-asserted-by":"publisher","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.\u00a023(4), 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR7","first-page":"51","volume":"10","author":"J.-P. Duval","year":"2005","unstructured":"Duval, J.-P., Lecroq, T., Lefebvre, 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_CR8","unstructured":"Duval, J.-P., Lecroq, T., Lefebvre, A.: Efficient validation and construction of Knuth-Morris-Pratt arrays. In: Conference in honor of Donald E. Knuth (2007)"},{"issue":"2","key":"13_CR9","first-page":"281","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. ITA\u00a043(2), 281\u2013297 (2009)","journal-title":"ITA"},{"key":"13_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, Washington, DC, USA, pp. 137\u2013143. IEEE Computer Society, Los Alamitos (1997)"},{"key":"13_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.\u00a042, 223\u2013236 (2002)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"13_CR12","doi-asserted-by":"publisher","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.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"13_CR13","doi-asserted-by":"publisher","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.\u00a047(2), 95\u201399 (1993)","journal-title":"Inf. Process. Lett."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"I, T., Inenaga, S., Bannai, H., Takeda, M.: Counting parameterized border arrays for a binary alphabet. In: Proc.\u00a0of the 3rd LATA, pp. 422\u2013433 (2009)","DOI":"10.1007\/978-3-642-00982-2_36"},{"key":"13_CR15","doi-asserted-by":"publisher","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)"},{"issue":"2","key":"13_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 Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","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\u00a023(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"issue":"1","key":"13_CR18","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"},{"key":"13_CR19","unstructured":"Morris Jr., J.H., Pratt, V.R.: A linear pattern-matching algorithm. Technical Report\u00a040, University of California, Berkeley (1970)"},{"issue":"2","key":"13_CR20","doi-asserted-by":"publisher","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\u00a051(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","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: Karhum\u00e4ki, J., Rozenberg, G., Maurer, H.A. (eds.) Results and Trends in Theoretical Computer Science. LNCS, vol.\u00a0812, pp. 386\u2013395. Springer, Heidelberg (1994)"},{"issue":"3","key":"13_CR22","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13182-0_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:02:18Z","timestamp":1606168938000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13182-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131813","9783642131820"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13182-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}