{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T07:06:52Z","timestamp":1773212812201,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1984,3,1]],"date-time":"1984-03-01T00:00:00Z","timestamp":446947200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1984,3]]},"DOI":"10.1007\/bf01934514","type":"journal-article","created":{"date-parts":[[2005,7,24]],"date-time":"2005-07-24T18:52:43Z","timestamp":1122231163000},"page":"45-59","source":"Crossref","is-referenced-by-count":68,"title":["Computing a longest common subsequence for a set of strings"],"prefix":"10.1007","volume":"24","author":[{"given":"W. J.","family":"Hsu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. W.","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"BF01934514_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"A. V. Aho","year":"1976","unstructured":"A. V. Aho, D. S. Hirschberg and J. D. Ullman,Bounds on the complexity of the longest common subsequence problem, J. Assoc. Comput. Mach. 23(1) (Jan. 1976), 1\u201312.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01934514_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1976","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman,The Design and Analysis of Computer Algorithms, 2nd printing, Addison-Wesley, Reading, Mass., 1976."},{"key":"BF01934514_CR3","first-page":"487","volume":"194","author":"V. L. Arlazarov","year":"1970","unstructured":"V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev,On economic construction of the transitive closure of a directed graph. Dokl. Akad. Nauk SSSR 194 (1970), 487\u2013488 (in Russian), English transl. in Soviet Math., Dokl. 11, 5 (1970), 1209\u20131210.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"BF01934514_CR4","first-page":"26","volume-title":"Selected combinatorial research problems","author":"V. Chavatal","year":"1972","unstructured":"V. Chavatal, D. A. Klarner, and D. E. Knuth,Selected combinatorial research problems, STAN-CS-72-292, Stanford Univ., Stanford, Calif. 1972, p. 26."},{"key":"BF01934514_CR5","volume-title":"Longest common subsequences of two random sequences","author":"V. Chvatal","year":"1975","unstructured":"V. Chvatal and D. Sankoff,Longest common subsequences of two random sequences. STAN-CS-75-477, Stanford Univ., Stanford, Calif., Jan. 1975."},{"key":"BF01934514_CR6","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0022-5193(65)90096-2","volume":"8","author":"M. O. Dayhoff","year":"1965","unstructured":"M. O. Dayhoff,Computer aids to protein sequence determination, J. Theoret. Biology 8, (Jan. 1965), 97\u2013112.","journal-title":"J. Theoret. Biology"},{"issue":"1","key":"BF01934514_CR7","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1038\/scientificamerican0769-86","volume":"221","author":"M. O. Dayhoff","year":"1969","unstructured":"M. O. Dayhoff,Computer analysis of protein evolution, Scientif. Amer. 221, 1 (July 1969), 86\u201395.","journal-title":"Scientif. Amer."},{"issue":"1","key":"BF01934514_CR8","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M. L. Fredman","year":"1975","unstructured":"M. L. Fredman,On computing length of the longest increasing subsequences, Discrete Math. 11, 1 (Jan. 1975), 29\u201336.","journal-title":"Discrete Math."},{"issue":"12","key":"BF01934514_CR9","first-page":"1087","volume":"C-12","author":"K. S. Fu","year":"1973","unstructured":"K. S. Fu and B. K. Bhargava,Tree systems for syntactic pattern recognition, IEEE Trans. Computs. C-12, 12 (Dec. 1973), 1087\u20131099.","journal-title":"IEEE Trans. Computs."},{"key":"BF01934514_CR10","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"J. Gallant, D. Maier and J. A. Storer,On finding minimal length superstrings, J. Comput. and Sys. Sci. 20, (1980), 50\u201358.","journal-title":"J. Comput. and Sys. Sci."},{"issue":"6","key":"BF01934514_CR11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D. S. Hirschberg","year":"1975","unstructured":"D. S. Hirschberg,A linear space algorithm for computing maximal common subsequences, Comm. ACM 18(6) (June, 1975), 341\u2013343.","journal-title":"Comm. ACM"},{"issue":"4","key":"BF01934514_CR12","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D. S. Hirschberg","year":"1977","unstructured":"D. S. Hirschberg,Algorithms for the longest common subsequence problem, J. Assoc. Comput. Mach. 24(4) (1977) 664\u2013675.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01934514_CR13","unstructured":"W. J. Hsu and M. W. Du,A fast algorithm for the longest common subsequence problem, Yearly Report for NSC Support, March (1982)."},{"key":"BF01934514_CR14","unstructured":"J. W. Hunt and M. D. McIlroy,An algorithm for Differential File Comparison, Computing Science Technical Report 41, 197."},{"issue":"5","key":"BF01934514_CR15","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J. W. Hunt","year":"1977","unstructured":"J. W. Hunt and T. G. Szymanski,A fast algorithm for computing longest common subsequences, Com. ACM 20(5) (May, 1977), 350\u2013353.","journal-title":"Com. ACM"},{"key":"BF01934514_CR16","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1007\/BF01934067","volume":"21","author":"S. Y. Itoga","year":"1981","unstructured":"S. Y. Itoga,The string merging problem, BIT 21 (1981), 20\u201330.","journal-title":"BIT"},{"key":"BF01934514_CR17","unstructured":"D. E. Knuth, J. H. Morris and V. R. Pratt,Fast pattern matching algorithms, Technical Report STAN-CS-74-440, Computer Science Dpet., Stanford Univ., Aug. (1974)."},{"key":"BF01934514_CR18","volume-title":"The Art of Computer Programming, Vol. 1:Fundamental Algorithms","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 1:Fundamental Algorithms, Addison-Wesley, Reading, Mass., Sec. ed., (1973).","edition":"Sec. ed."},{"key":"BF01934514_CR19","volume-title":"The Art of Computer Programming, Vol. 3:Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching, Addison-Wesley, Reading, Mass., (1973)."},{"issue":"2","key":"BF01934514_CR20","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/321879.321880","volume":"22","author":"R. Lowrance","year":"1975","unstructured":"R. Lowrance and R. A. Wagner,An extension of the string to string correction problem, J. Assoc., Comput. Mach., 22(2), (1975), 177\u2013183.","journal-title":"J. Assoc., Comput. Mach."},{"issue":"5","key":"BF01934514_CR21","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/TSMC.1978.4309979","volume":"SMC-8","author":"S. Y. Lu","year":"1978","unstructured":"S. Y. Lu and K. S. Fu,A sentence-to-sentence clustering procedure for pattern analysis, IEEE Trans. Syst., Man., Cybern., Vol. SMC-8(5), (May, 1978), 381\u2013389.","journal-title":"IEEE Trans. Syst., Man., Cybern."},{"issue":"2","key":"BF01934514_CR22","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier,The complexity of some problems on subsequences and supersequences, J. Assoc. Comput. Mach. 25(2), (April, 1978), 322\u2013336.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01934514_CR23","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. J. Masek","year":"1980","unstructured":"W. J. Masek and M. S. Paterson,A faster algorithm computing string edit distances, J. Comput. and Syst. Sci. 20 (1980), 18\u201331.","journal-title":"J. Comput. and Syst. Sci."},{"issue":"2","key":"BF01934514_CR24","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1145\/362007.362033","volume":"13","author":"H. L. Morgan","year":"1970","unstructured":"H. L. Morgan,Spelling correction in systems programs, Comm. ACM 13(2), (Feb. 1970), 90\u201394.","journal-title":"Comm. ACM"},{"key":"BF01934514_CR25","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0020-0255(80)90025-0","volume":"20","author":"A. Mukhopadhyay","year":"1980","unstructured":"A. Mukhopadhyay,A fast algorithm for the longest-common-subsequence problem, Inf. Sci. 20, (1980), 69\u201382.","journal-title":"Inf. Sci."},{"key":"BF01934514_CR26","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"D. Sankoff,Matching sequences under deletion insertion constraints, Proc. Nat. Acad. Sci., U.S.A., 69 (1972), 4\u20136.","journal-title":"Proc. Nat. Acad. Sci., U.S.A."},{"issue":"6","key":"BF01934514_CR27","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","volume":"6","author":"S. M. Selkow","year":"1977","unstructured":"S. M. Selkow,The tree-to-tree editing problem, Inform. Processing Letters, 6, 6 (Dec., 1977), 184\u2013186.","journal-title":"Inform. Processing Letters"},{"key":"BF01934514_CR28","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0097-3165(74)90050-8","volume":"A16","author":"P. H. Sellers","year":"1974","unstructured":"P. H. Sellers,An algorithm for the distance between two finite sequences, J. Combinatorial Theory Ser. A16: (1974), 253\u2013258.","journal-title":"J. Combinatorial Theory Ser."},{"issue":"3","key":"BF01934514_CR29","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1145\/361972.361982","volume":"16","author":"R. A. Wagner","year":"1973","unstructured":"R. A. Wagner,Common phrases and minimum-space text storage, Comm. ACM, 16(3), (March, 1973), 148\u2013152.","journal-title":"Comm. ACM"},{"issue":"1","key":"BF01934514_CR30","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"R. A. Wagner and M. J. Fischer,The string-to-string correction problem, J. Assoc. Comput. Mach. 21(1), (1974), 168\u2013173.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01934514_CR31","doi-asserted-by":"crossref","unstructured":"P. A. Wagner,On the complexity of the extended string-to-string correction problem. Proc. Seventh Annual ACM Symp. on Theory of Comput., (1975), 218\u2013223.","DOI":"10.1145\/800116.803771"},{"issue":"1","key":"BF01934514_CR32","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/321921.321923","volume":"28","author":"C. K. Wong","year":"1976","unstructured":"C. K. Wong and A. K. Chandra,Bounds for the string editing problem, J. Assoc. Comput. Mach. 28(1) (Feb. 1976), 13\u201318.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01934514_CR33","volume-title":"Fundamentals of Data Structures","author":"E. Horowitz","year":"1976","unstructured":"E. Horowitz and S. Sahni,Fundamentals of Data Structures, Computer Science Press, Potomac, Maryland, (1976)."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01934514.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01934514\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01934514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T01:10:02Z","timestamp":1557450602000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01934514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1984,3]]}},"alternative-id":["BF01934514"],"URL":"https:\/\/doi.org\/10.1007\/bf01934514","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,3]]}}}