{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:30Z","timestamp":1759637910644},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,12,5]],"date-time":"2007-12-05T00:00:00Z","timestamp":1196812800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00453-007-9141-3","type":"journal-article","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T16:16:13Z","timestamp":1196957773000},"page":"60-70","source":"Crossref","is-referenced-by-count":20,"title":["Indexing Factors with Gaps"],"prefix":"10.1007","volume":"55","author":[{"given":"Costas S.","family":"Iliopoulos","sequence":"first","affiliation":[]},{"given":"M. Sohel","family":"Rahman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,12,5]]},"reference":[{"key":"9141_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/3-540-45749-6_6","volume-title":"ESA","author":"P.K. Agarwal","year":"2002","unstructured":"Agarwal, P.K., Govindarajan, S., Muthukrishnan, S.: Range searching in categorical data: Colored range searching on grid. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA. Lecture Notes in Computer Science, vol.\u00a02461, pp.\u00a017\u201328. Springer, New York (2002)"},{"key":"9141_CR2","unstructured":"Allali, J., Sagot, M.-F.: The at most k-deep factor tree. Report 2004-03, Institut Gaspard Monge, Universit\u00e9 de Marne-la-Vall\u00e9e (2004)"},{"key":"9141_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: New data structures for orthogonal range searching. In: FOCS, pp.\u00a0198\u2013207 (2000)","DOI":"10.1109\/SFCS.2000.892088"},{"key":"9141_CR4","series-title":"NATO ISI Series","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-642-82456-2_6","volume-title":"Combinatorial Algorithms on Words","author":"A. Apostolico","year":"1985","unstructured":"Apostolico, A.: The myriad virtues of subword trees. In: Combinatorial Algorithms on Words. NATO ISI Series, pp.\u00a085\u201396. Springer, Berlin (1985)"},{"key":"9141_CR5","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1186\/1471-2105-4-66","volume":"4","author":"M. Brudno","year":"2003","unstructured":"Brudno, M., Chapman, M., G\u00f6ttgens, B., Batzoglou, S., Morgenstern, B.: Fast and sensitive multiple alignment of large genomic sequences. BMC Bioinf. 4, 66 (2003)","journal-title":"BMC Bioinf."},{"issue":"4","key":"9141_CR6","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1101\/gr.926603","volume":"13","author":"M. Brudno","year":"2003","unstructured":"Brudno, M., Do, C.B., Cooper, G.M., Kim, M.F., Davydov, E., Green, E.D., Sidow, A., Batzoglou, S.: Lagan and multi-lagan: Efficient tools for large-scale multiple alignment of genomic dna. Genome Res. 13(4), 721\u2013731 (2003)","journal-title":"Genome Res."},{"key":"9141_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/1007352.1007374","volume-title":"STOC","author":"R. Cole","year":"2004","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Babai, L. (ed.) STOC, pp.\u00a091\u2013100. ACM, Singapore (2004)"},{"key":"9141_CR8","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, Singapore (2002)"},{"issue":"1\u20133","key":"9141_CR9","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.tcs.2006.06.029","volume":"362","author":"M. Crochemore","year":"2006","unstructured":"Crochemore, M., Iliopoulos, C.S., Mohamed, M., Sagot, M.-F.: Longest repeats with a block of don\u2019t cares. Theor. Comput. Sci. 362(1\u20133), 248\u2013254 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9141_CR10","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","volume":"32","author":"R.C. Edgar","year":"2004","unstructured":"Edgar, R.C.: Muscle: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res. 32(5), 1792\u20131797 (2004)","journal-title":"Nucleic Acids Res."},{"key":"9141_CR11","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: FOCS, pp.\u00a0137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"9141_CR12","first-page":"491","volume-title":"VLDB","author":"L. Gravano","year":"2001","unstructured":"Gravano, L., Ipeirotis, P.G., Jagadish, H.V., Koudas, N., Muthukrishnan, S., Srivastava, D.: Approximate string joins in a database (almost) for free. In: Apers, P.M.G., Atzeni, P., Ceri, S., Paraboschi, S., Ramamohanarao, K., Snodgrass, R.T. (eds.) VLDB, pp.\u00a0491\u2013500. Morgan Kaufmann, San Mateo (2001)"},{"key":"9141_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"9141_CR14","doi-asserted-by":"crossref","unstructured":"H\u00f6hl, M., Kurtz, S., Ohlebusch, E.: Efficient multiple genome alignment. In: ISMB, pp.\u00a0312\u2013320 (2002)","DOI":"10.1093\/bioinformatics\/18.suppl_1.S312"},{"issue":"6","key":"9141_CR15","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1142\/S0129054105003716","volume":"16","author":"C.S. Iliopoulos","year":"2005","unstructured":"Iliopoulos, C.S., McHugh, J.A.M., Peterlongo, P., Pisanti, N., Rytter, W., Sagot, M.-F.: A first approach to finding common motifs with gaps. Int. J. Found. Comput. Sci. 16(6), 1145\u20131154 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9141_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"ICALP","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP. Lecture Notes in Computer Science, vol.\u00a02719, pp.\u00a0943\u2013955. Springer, New York (2003)"},{"issue":"2\u20134","key":"9141_CR17","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"D.K. Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J.\u00a0Discrete Algorithms 3(2\u20134), 126\u2013142 (2005)","journal-title":"J.\u00a0Discrete Algorithms"},{"issue":"2\u20134","key":"9141_CR18","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.\u00a0Discrete Algorithms 3(2\u20134), 143\u2013156 (2005)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9141_CR19","first-page":"164","volume":"14","author":"M. Li","year":"2003","unstructured":"Li, M., Ma, B., Kisman, D., Tromp, J.: Patternhunter ii: Highly sensitive and fast homology search. Genome Inf. 14, 164\u2013175 (2003)","journal-title":"Genome Inf."},{"issue":"3","key":"9141_CR20","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","volume":"18","author":"B. Ma","year":"2002","unstructured":"Ma, B., Tromp, J., Li, M.: Patternhunter: faster and more sensitive homology search. Bioinformatics 18(3), 440\u2013445 (2002)","journal-title":"Bioinformatics"},{"key":"9141_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/11496656_3","volume-title":"CPM","author":"M.G. Maa\u00df","year":"2005","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM. Lecture Notes in Computer Science, vol.\u00a03537, pp.\u00a021\u201332. Springer, New York (2005)"},{"issue":"4","key":"9141_CR22","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1016\/j.jda.2006.11.001","volume":"5","author":"M.G. Maa\u00df","year":"2007","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. J. Discrete Algorithms 5(4), 662\u2013681 (2007). doi:10.1016\/j.jda.2006.11.001, selected papers from Combinatorial Pattern Matching (CPM) 2005, December 2007","journal-title":"J. Discrete Algorithms"},{"issue":"5","key":"9141_CR23","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: 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":"9141_CR24","first-page":"262","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J.\u00a0ACM 23(2), 262\u2013272 (1976)","journal-title":"J.\u00a0ACM"},{"issue":"9","key":"9141_CR25","doi-asserted-by":"crossref","first-page":"2093","DOI":"10.1093\/bioinformatics\/bti224","volume":"21","author":"M. Michael","year":"2005","unstructured":"Michael, M., Dieterich, C., Vingron, M.: Siteblast-rapid and sensitive local alignment of genomic sequences employing motif anchors. Bioinformatics 21(9), 2093\u20132094 (2005)","journal-title":"Bioinformatics"},{"key":"9141_CR26","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp.\u00a0657\u2013666 (2002)"},{"key":"9141_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/3-540-45123-4_29","volume-title":"CPM","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Sutinen, E., Tanninen, J., Tarhio, J.: Indexing text with approximate q-grams. In: Giancarlo, R., Sankoff, D. (eds.) CPM. Lecture Notes in Computer Science, vol.\u00a01848, pp.\u00a0350\u2013363. Springer, New York (2000)"},{"key":"9141_CR28","first-page":"182","volume-title":"Stringology","author":"P. Peterlongo","year":"2006","unstructured":"Peterlongo, P., Allali, J., Sagot, M.-F.: The gapped-factor tree. In: Holub, J., Zd\u00e1rek, J. (eds.) Stringology, pp.\u00a0182\u2013196. Czech Technical University, Prague (2006)"},{"key":"9141_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/978-3-540-69507-3_40","volume-title":"SOFSEM (1)","author":"M.S. Rahman","year":"2007","unstructured":"Rahman, M.S., Iliopoulos, C.S.: Indexing factors with gaps. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plasil, F. (eds.) SOFSEM (1). Lecture Notes in Computer Science, vol.\u00a04362, pp.\u00a0465\u2013474. Springer, New York (2007)"},{"key":"9141_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/11809678_17","volume-title":"COCOON","author":"M.S. Rahman","year":"2006","unstructured":"Rahman, M.S., Iliopoulos, C.S., Lee, I., Mohamed, M., Smyth, W.F.: Finding patterns with variable length gaps or don\u2019t cares. In: Chen, D.Z., Lee, D.T. (eds.) COCOON. Lecture Notes in Computer Science, vol.\u00a04112, pp.\u00a0146\u2013155. Springer, New York (2006)"},{"key":"9141_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/3-540-60313-1_153","volume-title":"ESA","author":"E. Sutinen","year":"1995","unstructured":"Sutinen, E., Tarhio, J.: On using q-gram locations in approximate string matching. In: Spirakis, P.G. (ed.) ESA. Lecture Notes in Computer Science, vol.\u00a0979, pp.\u00a0327\u2013340. Springer, Berlin (1995)"},{"issue":"3","key":"9141_CR32","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9141-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9141-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9141-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T04:49:23Z","timestamp":1684126163000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9141-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,5]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9141"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9141-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,5]]}}}