[Seminar] locating all maximal approximate runs in a string
University of Haifa
■호스트:박근수 교수(x8381, 880-8381)
Professor Landau received his Ph.D. in Computer Science from Tel Aviv University in 1987. From 1988 to the present he has held positions as Assistant, Associate, and Research Professor at Polytechnic University in New York (now called NYU Polytechnic School of Engineering, New York University). In 1995, Landau joined the faculty of the University of Haifa, where he founded the Department of Computer Science and was the first department head. In 2006, Landau was promoted to his current position of full Professor at the University of Haifa. Landau's research interests focus on string algorithms, data structures, computational biology, and parallel computation. He has made several profound contributions to these areas, even in the early days of his scientific career. His Ph.D. thesis includes the fundamental text-book solution for the k-differences problem, solving one of the major open problems in the area at the time. His solution was the first to combine suffix trees and lowest common ancestor queries, and has since inspired many extensions of this technique to other problems.
An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n, finding all maximal exact runs in the string can be done in O(n log n) time on general ordered alphabets or O(n) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k, find non-empty substrings T' of T such that changing at most k letters in T' transforms them into a maximal exact run. We present an O(nk^2 log^2 k + occ) algorithm to solve this problem, where occ is the number of substrings found. 입니다.