{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:33:55Z","timestamp":1790843635558,"version":"4.1.0"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319674278","type":"print"},{"value":"9783319674285","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-67428-5_22","type":"book-chapter","created":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T21:22:24Z","timestamp":1504560144000},"page":"254-270","source":"Crossref","is-referenced-by-count":5,"title":["Detecting One-Variable Patterns"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Kosolobov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jda.2006.10.001","volume":"5","author":"A Amir","year":"2007","unstructured":"Amir, A., Nor, I.: Generalized function matching. J. Discrete Algorithms 5, 514\u2013523 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci. 21, 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR3","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\" theorem. arXiv preprint arXiv:1406.0263v4 (2014)"},{"key":"22_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-16321-0_27","volume-title":"String Processing and Information Retrieval","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Extracting powers and periods in a string from its runs structure. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol. 6393, pp. 258\u2013269. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-16321-0_27"},{"key":"22_CR5","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 Co., Pte. Ltd., Singapore (2002)"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-642-02737-6_14","volume-title":"Developments in Language Theory","author":"E Czeizler","year":"2009","unstructured":"Czeizler, E., Czeizler, E., Kari, L., Seki, S.: An extension of the Lyndon Sch\u00fctzenberger result to pseudoperiodic words. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 183\u2013194. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02737-6_14"},{"key":"22_CR7","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0020-0190(79)90135-2","volume":"9","author":"A Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, A., Rozenberg, G.: Finding a homomorphism between two words is NP-complete. Inform. Proc. Lett. 9, 86\u201388 (1979)","journal-title":"Inform. Proc. Lett."},{"key":"22_CR8","unstructured":"Fernau, H., Manea, F., Merca\u015f, R., Schmid, M.L.: Revisiting Shinohara\u2019s algorithm for computing descriptive patterns. Theor. Comput. Sci. (to appear)"},{"key":"22_CR9","unstructured":"Fernau, H., Manea, F., Merca\u015f, R., Schmid, M.L.: Pattern matching with variables: fast algorithms and new hardness results. In: Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, STACS 2015, LIPIcs, vol. 30, pp. 302\u2013315 (2015)"},{"key":"22_CR10","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly, Sebastopol (2006)","edition":"3"},{"issue":"1","key":"22_CR11","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/322047.322056","volume":"25","author":"Z Galil","year":"1978","unstructured":"Galil, Z., Seiferas, J.: A linear-time on-line recognition algorithm for \u201cpalstar\u201d. J. ACM 25(1), 102\u2013111 (1978)","journal-title":"J. ACM"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/978-3-662-44777-2_38","volume-title":"Algorithms - ESA 2014","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Lewenstein, M., Nicholson, P.K.: Weighted ancestors in suffix trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 455\u2013466. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44777-2_38"},{"key":"22_CR13","unstructured":"Gawrychowski, P., Manea, F., Nowotka, D.: Testing generalised freeness of words. In: Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, STACS 2014, LIPIcs, vol. 25, pp. 337\u2013349 (2014)"},{"key":"22_CR14","doi-asserted-by":"crossref","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, 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. In: SODA 2015, pp. 532\u2013551. SIAM (2015)","DOI":"10.1137\/1.9781611973730.36"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: FOCS 1999, pp. 596\u2013604. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814634"},{"key":"22_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/978-3-319-19929-0_25","volume-title":"Combinatorial Pattern Matching","author":"D Kosolobov","year":"2015","unstructured":"Kosolobov, D.: Online detection of repetitions with backtracking. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 295\u2013306. Springer, Cham (2015). doi: 10.1007\/978-3-319-19929-0_25"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Kosolobov, D., Manea, F., Nowotka, D.: Detecting one-variable patterns. arXiv preprint arXiv:1604.00054 (2016)","DOI":"10.1007\/978-3-319-67428-5_22"},{"key":"22_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-662-46078-8_24","volume-title":"SOFSEM 2015: Theory and Practice of Computer Science","author":"D Kosolobov","year":"2015","unstructured":"Kosolobov, D., Rubinchik, M., Shur, A.M.: Pal k is linear recognizable online. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 289\u2013301. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-46078-8_24"},{"key":"22_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). Chap. 3"},{"issue":"3","key":"22_CR21","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1145\/321892.321896","volume":"22","author":"G Manacher","year":"1975","unstructured":"Manacher, G.: A new linear-time on-line algorithm finding the smallest initial palindrome of a string. J. ACM 22(3), 346\u2013351 (1975)","journal-title":"J. ACM"},{"key":"22_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-662-44522-8_34","volume-title":"Mathematical Foundations of Computer Science 2014","author":"F Manea","year":"2014","unstructured":"Manea, F., M\u00fcller, M., Nowotka, D., Seki, S.: Generalised Lyndon-Sch\u00fctzenberger equations. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 402\u2013413. Springer, Heidelberg (2014). doi: 10.1007\/978-3-662-44522-8_34"},{"key":"22_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-319-29516-9_27","volume-title":"Combinatorial Algorithms","author":"M Rubinchik","year":"2016","unstructured":"Rubinchik, M., Shur, A.M.: EERTREE: an efficient data structure for processing palindromes in strings. In: Lipt\u00e1k, Z., Smyth, W.F. (eds.) IWOCA 2015. LNCS, vol. 9538, pp. 321\u2013333. Springer, Cham (2016). doi: 10.1007\/978-3-319-29516-9_27"},{"key":"22_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2016.02.003","volume":"249","author":"ML Schmid","year":"2016","unstructured":"Schmid, M.L.: Characterising REGEX languages by regular languages equipped with factor-referencing. Inf. Comput. 249, 1\u201317 (2016)","journal-title":"Inf. Comput."},{"key":"22_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-13509-5_6","volume-title":"Combinatorial Pattern Matching","author":"Z Xu","year":"2010","unstructured":"Xu, Z.: A minimal periods algorithm with applications. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 51\u201362. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13509-5_6"}],"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-319-67428-5_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T23:59:44Z","timestamp":1570060784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67428-5_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319674278","9783319674285"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67428-5_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}