Литература

Aho A.V., Hopcroft J.E., Ullman J.D. (1974) "The design and analysis of computer algorithms," Addison-Wesley, Reading, MA.

Aho A.V., Corasick M.J. (1975) "Efficient string matching: an aid to bibliographic search," Communications of the ACM, Vol. 18, No. 6, p. 333-40, June 1975.

Aho A.V., Hirschberg D.S., Ullman J.D. (1976) "Bounds on the complexity of the longest common subsequence problem," Journal of the ACM, Vol. 23, No. 1, p. 1-12, January1976.

Aho A.V. (1980) "Pattern matching in strings," in Book R.V. (ed.) Formal Language Theory, p. 325-47, Academic Press, New York.

Aho A.V., Sethi R., Ullman J.D. (1986) Compilers – Principles, Techniques, and Tools, Addison-Wesley, Reading, MA.

Aho A.V. (1990) "Algorithms for finding patterns in strings," Chapter 5 (p. 255-300) of Leeuwen J. van (ed.) Handbook of Theoretical Computer Science, Elsevier Science Publishers, Amsterdam.

Altschul S.F., Gish W., Miller W., Myers E.W., Lipman D.J. (1990) "Basic local alignment search tool," Journal of Molecular Biology, Vol. 215, p. 403-10.

Apostolico A. (1985) "The myriad virtues of subword trees," in Apostolico A., Galil Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series, Vol. F12, p. 85-96, Springer-Verlag, Berlin.

Apostolico A., Giancarlo R. (1986) "The Boyer-Moore-Galil string searching strategies revisited," SIAM Journal on Computing, Vol. 15, No. 1, p. 98-105, February 1986.

Apostolico A., Guerra C. (1987) "The longest common subsequence problem revisited," Algorithmica, Vol. 2, p. 315-36.

Apostolico A., Iliopoulos C., Landau G.M., Schieber B., Vishkin U. (1988) "Parallel construction of a suffix tree with applications," Algorithmica, Vol. 3, p. 347-65.

Arlazarov V.L., Dinic E.A., Kronod M.A., Faradzev I.A. (1970) "On economic construction of the transitive closure of a directed graph," (Russian) Doklady Akademii Nauk SSR, Vol. 194, p. 487-8, also translated in Soviet Math. Doklady, Vol. 11, p. 1209-10, 1975.

Arratia R., Waterman M.S. (1985a) "Critical phenomena in sequence matching," The Annals of Probability, Vol. 13, No. 4, p. 1236-49.

Arratia R., Waterman M.S. (1985b) "An Erdцs-Rйnyi law with shifts," Advances in Mathematics, Vol. 55, p. 13-23.

Arratia R., Gordon L., Waterman M. (1986) "An extreme value theory for sequence matching," The Annals of Statistics, Vol. 14, No. 3, p. 971-93.

Bachman P. (1894) Die analytische Zahlentheorie, Teubner, Leipzig.

Baeza-Yates R.A. (1989a) "Improved string matching," Software – Practice and Experience, Vol. 19, No. 3, p. 257-71, March 1989.

Baeza-Yates R.A. (1989b) "String searching algorithms revisited," Lecture Notes in Computer Science, Vol. 382, p. 75-96.

Baeza-Yates R.A. (1991) "Searching subsequences," Theoretical Computer Science, Vol. 78, No. 2, p. 363-76.

Baker B.S. (1992) "A program for identifying duplicated code," Proceedings of the 24th Symposium on the Interface: Computer Science and Statistics, College Station, Texas, 18-21 March 1992.

Bellman R., Dreyfus S. (1962) "Applied Dynamic Programming," Princeton University Press, Princeton NJ.

Blumer A., Blumer J., Ehrenfeucht A., Haussler D., McConnel R. (1984a) "Building a complete inverted file for a set of text files in linear time," Proceedings of the 16^th ACM Symposium on the Theory of Computing, p. 349-58.

Blumer A., Blumer J., Ehrenfeucht A., Haussler D., McConnel R. (1984b) "Building the minimal DFA for the set of all subwords of a word on-line in linear time," in Paredaens J. (ed.), Proceedings of the 11th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 172, p. 109-18, Springer-Verlag, Berlin.

Blumer A., Blumer J., Ehrenfeucht A., Haussler D., Chen M.T., Seiferas J. (1985) "The smallest automaton recognizing the subwords of a word," Theoretical Computer Science, Vol. 40, No. 1, p. 31-56.

Blumer A., Blumer J., Haussler D., McConnel R., Ehrenfeucht A. (1987) "Complete inverted files for efficient text retrieval and analysis," Journal of the ACM, Vol. 34, No. 3, p. 578-95.

Bois-Reymond P. du(1871) "Sur la grandeur relative des infinis des fonctions," Annali di Matematica pura e applicata, series 2, Vol. 4, p. 338-53.

Boyer R.S., Moore J.S. (1977) "A fast string searching algorithm," Communications of the ACM, Vol. 20, No. 10, p. 762-72, October 1977.

Burkowski F.J. (1982) "A hardware hashing scheme in the design of a multiterm string comparator," IEEE Transactions on Computers, Vol. C-31, No. 9, p. 825-34, September 1982.

Chen M.T., Seiferas J. (1985) "Eficient and elegant subword-tree construction," in Apostolico A., Galil Z. (eds.) Combinatorial Algorithms on Words, NATO ASI Series, Vol. F12, p. 97-107, Springer-Verlag, Berlin.

Cook S.A. (1972) "Linear time simulation of deterministic two-way pushdown automata," Information Processing, Vol. 71, p. 75-80, North-Holland, Amsterdam.

Crochemore M. (1986) "Transducers and repetitions," Theoretical Computer Science, Vol. 45, p. 63-86.

Curry T., Mukhopadhyay A.(1983) "Realization of eficient non-numeric operations through VLSI," Proceedings of VLSI `83.

Davies G., Bowsher S. (1986) "Algorithms for pattern matching," Software – Practice and Experience, Vol. 16, No. 6, p. 575-601, June 1986.

Fischer M.J., Paterson M.S. (1974) "String-matching and other products," in Karp R.M. (ed.), Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, p. 113-25.

Foster M.J., Kung H.T. (1980) "The design of special-purpose VLSI chips," IEEE Computer, Vol. 13, p. 26-40, January 1980.

Galil Z. (1979) "On improving the worst case running time of the Boyer-Moore string searching algorithm," Communications of the ACM, Vol. 22, No. 9, p. 505-8.

Galil Z., Giancarlo R. (1986) "Improved string matching with k mismatches," Sigact News, Vol. 17, p. 52-4.

Galil Z., Giancarlo R. (1988) "Data structures and algorithms for approximate string matching," Journal of Complexity, Vol. 4, p. 33-72.

Gonnet G.H., Baeza-Yates R. (1991) "Text algorithms," Chapter 7 (p. 251-88) of Handbook of Algorithms and Data Structures in Pascal and C, 2^nd edition, Addison-Wesley, Wokingham UK.

Graham R.L., Knuth D.E., Patashnik O. (1990) Concrete Mathematics, Addison-Wesley, Reading, MA (5^th printing with corrections, July 1990).

Guibas L.J., Odlyzko A.M. (1977) "A new proof of the linearity of the Boyer-Moore string searching algorithm," Proceedings of the 18^th Annual IEEE Symposium on Foundations of Computer Science, p. 189-95 (also SIAM Journal on Computing, Vol. 9, No. 4, p. 672-82, 1980).

Halaas A. (1983) "A systolic VLSI matrix for a family of fundamental search problem," Integration VLSI Journal, Vol. 1, No. 4, p. 269-82, December 1983.

Hall P.A.V., Dowling G.R. (1980) "Approximate matching," Computing Surveys, Vol. 12, No. 4, p. 381-402, December 1980.

Hamming R. (1982) "Coding and Information Theory," Prentice Hall, Englewood Cliffs NJ.

Harel D., Tarjan R.E. (1984) "Fast algorithms for finding nearest common ancestors," SIAM Journal on Computing, Vol. 13, No. 2, p. 338-55.

Harrison M.C. (1971) "Implementation of the substring test by hashing," Communications of the ACM, Vol. 14, No. 12, p. 777-9, December 1971.

Haskin R.L. (1981) "Special purpose processors for text retrieval," Database Engineering, Vol. 4, No. 1, p. 16-29, September 1981.

Haskin R.L., Hollaar L.A (1983) "Operational characteristics of a hardware-based pattern matcher," ACM Transactions on Database Systems, Vol. 8, No. 1, p. 15-40, March 1983.

Haton J.P. (1973) "Contribution a l'analyse, parametrisation et la reconnaissance automatique de la parole," These de doctorat d'etat, Universitfie de Nancy, Nancy France.

Hirata M., Yamada H., Nagai H., Takahashi K. (1988) "A versatile data string-search VLSI," IEEE Journal of Solid-State Circuits, Vol. 23, No. 2, p. 329-35, April 1988.

Hirschberg D.S. (1975) "A linear space algorithm for computing maximal common subsequences," Communications of the ACM, Vol. 18, No. 6, p. 341-3, June 1975.

Hirschberg D.S. (1978) "An information theoretic lower bound for the longest common subsequence problem," Information Processing Letters, Vol. 7, p. 40-1.

Hirschberg D.S. (1983) "Recent results on the complexity of common subsequence problems," in Sankofi D., Kruskall J.B. (eds.) Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, Chapter 12, p. 325-30, Addison-Wesley, Reading MA.

Hollaar L.A. (1979) "Text retrieval computers," IEEE Computer, Vol. 12, p. 40-50.

Horspool R.N. (1980) "Practical fast searching in strings," Software – Practice and Experience, Vol. 10, No. 6, p. 501-6.

Hsu W., Du M. (1984) "Computing a longest common subsequence for a set of strings," BIT, Vol. 24, p. 45-59.

Hume A., Sunday D.(1991) "Fast string searching," Software – Practice and Experience, Vol. 21, No. 11, p. 1221-48, November 1991.

Hunt J.W., McIlroy M.D. (1976) "An algorithm for differential file comparison," Computing Science Technical Report 41, AT&T Bell Laboratories, Murray Hill NJ.

Hunt J.W., Szymanski T.G. (1977) "A fast algorithm for computing longest common subsequences," Communications of the ACM, Vol. 20, No. 5, p. 350-3, May 1977.

Ivanov A.G. (1984) "Distinguishing an approximate word's inclusion on Turing machine in real time," Izv. Akademii Nauk SSSR Ser. Mat., Vol. 48, p. 520-68 (Russian).

Jacobson G., Vo K-P. (1992) "Heaviest increasing/common subsequence problems," Proceedings of the Combinatorial Matching Conference, Tucson, Arizona, April 1992.

Karp R.M. (1972) "Reducibility among combinatorial problems," in Miller R.E., Thatcher J.W. (eds.) Complexity of Computer Computations, p. 85-103, Plenum Press.

Karp R.M., Rabin M.O. (1987) "Efficient randomized pattern-matching algorithms," IBM Journal of Research and Development, Vol. 31, No. 2, p. 249-60, March 1987.

Knuth D.E. (1973) "The art of computer programming, Volume 3: Sorting and Searching," Chapter 6.3, p. 490-3, Addison-Wesley, Reading MA.

Knuth D.E., Morris J.H., Pratt V.R. (1977) "Fast pattern matching in strings," SIAM Journal on Computing, Vol. 6, No. 2, p. 323-50, June 1977.

Landau G.M., Vishkin U., Nussinov R.(1985) "An efficient string matching algorithm with k differences for nucleotide and amino acid sequences," Technical Report TR-37/85, Department of Computer Science, Tel Aviv University.

Landau G.M., Vishkin U. (1985) "Efficient string matching in the presence of errors," Proceedings of the 26^th IEEE Symposium on the Foundations of Computer Science, p. 126-36.

Landau G.M., Vishkin U. (1986a) "Efficient string matching with k mismatches," Theoretical Computer Science, Vol. 43, p. 239-49.

Landau G.M., Vishkin U. (1986b) "Introducing efficient parallelism into approximate string matching and a new serial algorithm," Proceedings of the 18^th ACM Symposium on the Theory of Computing, p. 220-30.

Landau G.M., Schieber B., Vishkin U. (1987) "Parallel construction of a suffix tree," Proceedings of the 14th ICALP, Lecture Notes in Computer Science, Vol. 267, p. 314-25, Springer-Verlag, New York/Berlin.

Landau G.M., Vishkin U. (1988) "Fast string matching with k differences," Journal of Computer and System Sciences, Vol. 37, No. 1, p. 63-78.

Landau G.M., Vishkin U. (1989) "Fast parallel and serial approximate string matching," Journal of Algorithms, Vol. 10, p. 157-69.

Lee D., Lochovsky F. (1985) "Text retrieval machine," Office Automation – Concepts and Tools, section 14, Springer-Verlag, New York.

Lee K.C., Mak V.W. (1989) "Design and analysis of a parallel VLSI string search algorithm," Lecture Notes in Computer Science, Vol. 368, p. 215-29.

Levenshtein V.I. (1965) "Binary codes capable of correcting deletions, insertions, and reversals," (Russian) Doklady Akademii Nauk SSR, Vol. 163, No. 4, p. 845-8, also Cybernetics and Control Theory, Vol. 10, No. 8, p. 707-10, 1966.

Lipman D.J., Pearson W.R. (1985) "Rapid and sensitive protein similarity searches," Science, Vol. 227, No. 4693, p. 1435-41, 22 March 1985.

Lowrance R., Wagner R.A. (1975) "An extension of the string-to-string correction problem," Journal of the ACM, Vol. 22, No. 2, p. 177-83.

Maier D. (1978) "The complexity of some problems on subsequences and supersequences," Journal of the ACM, Vol. 25, No. 2, p. 322-36, April 1978.

Majster M.E., Reiser A. (1980) "Efficient on-line construction and correction of position trees," SIAM Journal on Computing, Vol. 9, No. 4, p. 785-807, November 1980.

Masek W.J., Paterson M.S. (1980) "A faster algorithm for computing string-edit distances," Journal of Computer and Systems Sciences, Vol. 20, No. 1, p. 18-31.

Masek W.J., Paterson M.S. (1983) "How to compute string-edit distances quickly," in Sankofi D., Kruskall J.B. (eds.) Time warps, string edits, and macromolecules: the theory and practice ofsequence comparison, Chapter 14, p. 337-49, Addison-Wesley, Reading MA.

McCreight E.M. (1976) "A space-economical suffix tree construction algorithm," Journal of the ACM, Vol. 23, No. 2, p. 262-72, April 1976.

Menico C. (1989) "Faster string searches," Dr. Dobb's Journal, p. 74-5, July 1989.

Morrison D.R. (1968) "PATRICIA – practical algorithm to retrieve information coded in alphanumeric," Journal of the ACM, Vol. 15, No. 4, p. 514-34.

Mukhopadhyay A.(1980) "Hardware algorithms for string processing," Proceedings of ICCC, p. 508-11.

Myers E.W. (1986) "An O(ND) difierence algorithm and its variations," Algorithmica, Vol. 1, p. 251-66.

Needleman S.B., Wunsch C.D. (1970) "A general method applicable to the search for similarities in the amino-acid sequence of two proteins," Journal of Molecular Biology, Vol. 48, p. 443-53.

Pinter R.Y. (1985) "Efficient string matching with don't care patterns," in Apostolico A., Galil Z. (eds.), Combinatorial Algorithms on Words, NATO ASI Series, Vol. F12, p. 11-29, Springer-Verlag, Berlin.

Pirklbauer K. (1992) "A study of pattern-matching algorithms," Structured Programming, Vol. 13, p. 89-98, Springer Verlag New York.

Regnier M. (1988) "Knuth-Morris-Pratt algorithm: an analysis," INRIA, Rocquencourt, France (unpublished).

Reichert T.A., Cohen D.N., Wong A.K.C. (1973) "An application of information theory to genetic mutations and the matching of polypeptide sequences," Journal of Theoretical Biology, Vol. 42, p. 245-61.

Rivest R.L. (1977) "On the worst-case behaviour of string searching algorithms," SIAM Journal on Computing, Vol. 6, No. 4, p. 669-74.

Robert D.C. (1982) "A specialized computer architecture for text retrieval," Proceedings of the 4^th Workshop on Computer Architecture, p. 51-9.

Rodeh M., Pratt V.R., Even S. (1981) "Linear algorithm for data compression via string matching," Journal of the ACM, Vol. 28, No. 1, p. 16-24, January 1981.

Rytter W. (1980) "A correct preprocessing algorithm for Boyer-Moore string-searching," SIAM Journal on Computing, Vol. 9, p. 509-12.

Sakoe H., Chiba S. (1970) "A similarity evaluation of speech patterns by dynamic programming," (Japanese) Institute of Electronic Communications Engineering of Japan, p. 136, July 1970.

Sakoe H., Chiba S. (1971) "A dynamic programming approach to continuous speech recognition," 1971 Proceedings of the International Congress of Acoustics, Budapest, Hungary, Paper 20 C 13.

Salton G. (1980) "Automatic information retrieval," IEEE Computer, Vol. 13, p. 41-55. September 1980.

Sankofi D. (1972) "Matching sequences under deletion-insertion constraints, " Proceedings of the National Academy of Sciences of the USA, Vol. 69, p. 4-6.

Sankofi D., Kruskall J.B. (eds.) (1983) "Time warps, string edits, and macromolecules: the theory and practice of sequence comparison," Addison-Wesley, Reading MA.

Schaback R.(1988) "On the expected sublinearity of the Boyer-Moore algorithm," SIAM Journal on Computing, Vol. 17, No. 4, p. 648-58.

Schensted C. (1961) "Largest increasing and decreasing subsequences," Canadian Journal of Mathematics, Vol. 13, p. 179-91.

Schieber B., Vishkin U. (1988) "On finding lowest common ancestors: simplification and parallelization," SIAM Journal on Computing, Vol. 17, No. 6, p. 1253-62.

Schцnhage A., Strassen V. (1971) "Schnelle Multiplikation grosser Zahlen," Computing (Arch. Elektron. Rechnen), Vol. 7, p. 281-92.

Sedgewick R.(1983) "String searching," Chapter 19 (p. 241-55) of Algorithms, Addison-Wesley, Reading MA.

Sellers P.H. (1980) "The theory and computation of evolutionary distances: pattern recognition," Journal of Algorithms, Vol. 1, p. 359-73.

Sibbald P.R., White M.J. (1987) "How probable are antibody cross-reactions?," Journal of Theoretical Biology, Vol. 127, p. 163-9.

Smit G. de V. (1982) "A comparison of three string matching algorithms," Software – Practice and Experience, Vol. 12, p. 57-66.

Smith P.D. (1991) "Experiments with a very fast substring search algorithm," Software – Practice and Experience, Vol. 21, No. 10, p. 1065-74, October 1991.

Smith T.F., Waterman M.S. (1981) "Identification of common molecular subsequences," Journal of Molecular Biology, Vol. 147, p. 195-7.

Sunday D.M. (1990) "A very fast substring search algorithm," Communications of the ACM, Vol. 33, No. 8, p. 132-42, August 1990.

Ukkonen E. (1983) "On approximate string matching," Proceedings of the International Conference on Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 158, p. 487-95, Springer-Verlag, Berlin.

Ukkonen E. (1985a) "Algorithms for approximate string matching," Information and Control, Vol. 64, p. 100-18.

Ukkonen E. (1985b) "Finding approximate patterns in strings," Journal of Algorithms, Vol. 6, No. 6, p. 132-7.

Velichko V.M., Zagoruyko N.G. (1970) "Automatic recognition of 200 words," International Journal of Man-Machine Studies, Vol. 2, p. 223-34.

Vintsyuk T.K. (1968) "Speech discrimination by dynamic programming," Cybernetics, Vol. 4, No. 1, p. 52-7, also (Russian) Kibernetika, Vol. 4, No. 1, p. 81-8.

Vo K-P. (1986) "More <curses>: the <screen> library,» Technical Report, AT&T Bell Laboratories.

Wagner R.A., Fischer M.J. (1974) "The string-to-string correction problem," Journal of the ACM, Vol. 21, No. 1, p. 168-73, January 1974.

Wagner R.A. (1975) "On the complexity of the extended string-to-string correction problem," Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, p. 218-23, also in Sankofi D., Kruskall J.B. (eds.) Time warps, string edits, and macromolecules: the theory and practice of sequence comparison, Addison-Wesley, Reading MA, 1983.

Weiner P. (1973) "Linear pattern matching algorithm," Proceedings of the 14^th IEEE Symposium on Switching and Automata Theory, p. 1-11.

Wong C.K., Chandra A.K. (1976) "Bounds for the string editing problem," Journal of the ACM, Vol. 23, No. 1, p. 13-6, January 1976.

Woude J. van der (1989) "Playing with patterns, searching for strings," Science of Computer Programming, Vol. 12, No. 3, p. 177-90, Elsevier Science Publishers.

Yamada H., Hirata M., Nagai H., Takahashi K. (1987) "A high-speed string-search engine," IEEE Journal of Solid-State Circuits, Vol. SC-22, No. 5, p. 829-34, October 1987.

Yianilos P.N. (1983) "A dedicated comparator matches symbol strings fast and intelligently," Electronics, Vol. 56, No. 5, p. 113-7, December 1983.

Ziv J., Lempel A. (1977) "A universal algorithm for sequential data compression," IEEE Transactions on Information Theory, Vol. IT-23, p. 337-43, May 1977.