{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:10:56Z","timestamp":1770487856007,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,8,17]],"date-time":"2016-08-17T00:00:00Z","timestamp":1471392000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"KAKENHI"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0178-z","type":"journal-article","created":{"date-parts":[[2016,8,17]],"date-time":"2016-08-17T13:26:45Z","timestamp":1471440405000},"page":"291-318","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient Computation of Substring Equivalence Classes with Suffix Arrays"],"prefix":"10.1007","volume":"79","author":[{"given":"Kazuyuki","family":"Narisawa","sequence":"first","affiliation":[]},{"given":"Hideharu","family":"Hiratsuka","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,17]]},"reference":[{"key":"178_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A Blumer","year":"1985","unstructured":"Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31\u201355 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"178_CR2","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., Mcconnell, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"key":"178_CR3","doi-asserted-by":"crossref","unstructured":"Crochemore, M., V\u00e9rin, R.: Direct construction of compact directed acyclic word graphs.In: Proceedings of CPM 1997, pp. 116\u2013129 (1997)","DOI":"10.1007\/3-540-63220-4_55"},{"issue":"6","key":"178_CR4","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"issue":"2","key":"178_CR5","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.dam.2004.04.012","volume":"146","author":"S Inenaga","year":"2005","unstructured":"Inenaga, S., Hoshinoa, H., Shinohara, A., Takeda, M., Arikawa, S., Mauri, G., Pavesi, G.: On-line construction of compact directed acyclic word graphs. Discret. Appl. Math. 146(2), 156\u2013179 (2005)","journal-title":"Discret. Appl. Math."},{"key":"178_CR6","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":"178_CR7","doi-asserted-by":"crossref","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Proceedings of CPM\u201901, pp. 181\u2013192 (2001)","DOI":"10.1007\/3-540-48194-X_17"},{"key":"178_CR8","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discret. Algorithms 3, 126\u2013142 (2005)","journal-title":"J. Discret. Algorithms"},{"key":"178_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discret. Algorithms 3, 143\u2013156 (2005)","journal-title":"J. Discret. Algorithms"},{"issue":"5","key":"178_CR10","doi-asserted-by":"crossref","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 string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"178_CR11","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"178_CR12","doi-asserted-by":"crossref","unstructured":"Narisawa, K., Bannai, H., Hatano, K., Takeda, M.: Unsupervised spam detection based on string alienness measures. In: Proceedings of DS\u201907, pp. 159\u2013172 (2007)","DOI":"10.1007\/978-3-540-75488-6_16"},{"key":"178_CR13","doi-asserted-by":"crossref","unstructured":"Narisawa, K., Inenaga, S., Bannai, H., Takeda, M.: Efficient computation of substring equivalence classes with suffix arrays. In: Proceedings of CPM\u201907, pp. 340\u2013351 (2007)","DOI":"10.1007\/978-3-540-73437-6_34"},{"issue":"10","key":"178_CR14","doi-asserted-by":"crossref","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G Nong","year":"2011","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Comput. 60(10), 1471\u20131484 (2011)","journal-title":"IEEE Trans. Comput."},{"key":"178_CR15","doi-asserted-by":"crossref","unstructured":"Okanohara, D., Tsujii, J.: Text categorization with all substring features. In: Proceedings of SDM\u201909, pp. 838\u2013846 (2009)","DOI":"10.1137\/1.9781611972795.72"},{"key":"178_CR16","unstructured":"Puglisi, S.J., Smyth, W.F., Yusufu, M.: Fast optimal algorithms for computing all the repeats in a string. In: Proceedings of PSC\u201908, pp. 161\u2013169 (2008)"},{"issue":"1","key":"178_CR17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(92)90142-3","volume":"92","author":"D Revuz","year":"1992","unstructured":"Revuz, D.: Minimisation of acyclic deterministic automata in linear time. Theor. Comput. Sci. 92(1), 181\u2013189 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"178_CR18","unstructured":"sais. \n                        https:\/\/sites.google.com\/site\/yuta256\/\n                        \n                     Accessed 30 Oct 2013"},{"issue":"2","key":"178_CR19","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1016\/S0304-3975(02)00185-8","volume":"292","author":"M Takeda","year":"2003","unstructured":"Takeda, M., Matsumoto, T., Fukuda, T., Nanri, I.: Discovering characteristic expressions in literary works. Theor. Comput. Sci. 292(2), 525\u2013546 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"178_CR20","unstructured":"The canterbury corpus. \n                        http:\/\/corpus.canterbury.ac.nz\/\n                        \n                     Accessed 30 Oct 2013"},{"issue":"3","key":"178_CR21","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)","journal-title":"Algorithmica"},{"key":"178_CR22","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of 14th IEEE Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0178-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0178-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0178-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0178-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T18:34:30Z","timestamp":1501526070000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0178-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,17]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["178"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0178-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,17]]}}}