An Efficient Real Scaled String Matching Algorithm

[[abstract]]本文搜尋廣泛地使用在科技上，例如：電腦科學、多媒體圖書館和web搜尋等，本文提出如何在本文中找出所有可能縮放大小下出現的pattern，此縮放大小加入適合實數縮放，本文將合適的實數縮放分為大於等於一和小於等於一兩種情況加以探討，並利用實數縮放索引樹(Real Scaled Indexing Tree, RSIT)來舉例說明，子字串在各種縮放大小下與本文比對結果是否吻合。在給定本文長度為n和pattern長度為m下，本文時間複雜度為O(n^3)。[[abstract]]Text searching is used on a wide variety of technologies, such as computer science, multimedia library, web search, etc. This thesis proposes how to find all possible patterns that appear under the real scales in text. On our algorithm, we consider two cases of real scales. One of them contains the scale range is greater than or equal to 1. The other case contains the range is less than or equal to 1. By using the Real Scaled Indexing Tree (RSIT), we can determine whether a substring under every scale can match the text or not. Assume that the lengths of text and pattern length are n and m, respectively. The time complexity is O(n^3).[[note]]碩