An Approximate String Matching Based on an Exact String Matching with Constant Pattern Length

[[abstract]]字串比對在許多領域當中是非常重要的問題，比方說電腦科學、生物資訊學與其他領域的問題。 精確字串比對問題是說，我們給定兩個字串，一個是長度為n的字串T，另一個是長度為M的字串P，m≦n，我們要在T上面找到所有P所發生的位置。而這裡的近似字串比對是說，在字串T上，以第i個字為終結的字首當中，我們要在這字首當中找一個字尾，使得這個字尾跟字串P的編輯距離小於等於k。 本篇論文是利用精確字串比對的特性來解決近似字串比對的問題。[[abstract]]The string matching problem is a very important problem which is needed to solve in computer science, computational biology and other domains. The exact matching problem is defined as follows: Given a string T whose length is n and a string P whose length is m, m≦n, find each location where string P occurs in string T. The approximate string matching problem is defined as follows: Given a pattern string P of length m and a text string T of length n, m≦n, and a maximal number k of errors allowed, find each location i of T such that there exists a suffix A of T(0,i) and ED(A,B)≦k. In our thesis, we will use the exact string matching to solve the approximate string matching problem.[[note]]碩