請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96345完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂 | zh_TW |
| dc.contributor.advisor | Kun-Mao Chao | en |
| dc.contributor.author | 黃品淳 | zh_TW |
| dc.contributor.author | Pin-Chun Huang | en |
| dc.date.accessioned | 2024-12-24T16:27:27Z | - |
| dc.date.available | 2024-12-25 | - |
| dc.date.copyright | 2024-12-24 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-11-07 | - |
| dc.identifier.citation | [1] S. Alstrup, G. Brodal, and T. Rauhe. New data structures for orthogonal range searching. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 198–207, 2000.
[2] A. Amir, P. Charalampopoulos, S. Pissis, and J. Radoszewski. Dynamic and internal longest common substring. Algorithmica, 82(12):3707–3743, 2020. [3] M. Berg, O. Cheong, M. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 2008. [4] T. M. Chan. Persistent predecessor search and orthogonal point location on the word ram. ACM Transactions on Algorithms, pages 1–22, 2013. [5] K.-Y. Chen, P.-H. Hsu, and K.-M. Chao. Efficient retrieval of approximate palindromes in a run-length encoded string. Theoretical Computer Science, pages 28–37, 2012. [6] J. Fischer and V. Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM Journal on Computing, 40(2):465–492, 2011. [7] D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. [8] D. Harel and R. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984. [9] P.-H. Hsu, K.-Y. Chen, and K.-M. Chao. Finding all approximate gapped palindromes. In Proceedings of the 20th International Symposium on Algorithms And Computation, pages 1084–1093, 2009. [10] G. Manacher. A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string. J. ACM, 22(3):346–351, 1975. [11] K. Mitani, T. Mieno, K. Seto, and T. Horiyama. Internal longest palindrome queries in optimal time. In Proceedings of the 17th International Conference and Workshops on Algorithms and Computation, pages 127–138, 2023. [12] S. Narisada, D. Hendrian, K. Narisawa, S. Inenaga, and A. Shinohara. Efficient computation of longest single-arm-gapped palindromes in a string. Theoretical Computer Science, pages 160–173, 2020. [13] M. Rubinchik and A. Shur. Eertree: An efficient data structure for processing palindromes in strings. European Journal of Combinatorics, 68:249–265, 2018. [14] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96345 | - |
| dc.description.abstract | 給定一個長度為n的字串T以及一個正整數k，我們設計出一個有效率的演算法，對於字串T進行前處理後，可以在後續指定的任意子字串中快速找出該範圍內最長的近似迴文。近似迴文在此定義為左右兩半至多有k 個不對稱字元的字串。我們設計出的演算法在前處理所需的時間及空間複雜度分別為O(kn)以及O(n)，後續每次查詢某段範圍內最長近似迴文所需要的計算時間為O(log log n)。 | zh_TW |
| dc.description.abstract | Given an input string T of length n and an integer k, we study how to find the longest k-mismatch palindromic substring within a range specified by each query. For this problem, we propose an algorithm with O(kn) preprocessing time and O(n) space, enabling each query to be answered in O(log log n) time on the word RAM model. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-12-24T16:27:27Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-12-24T16:27:27Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements i
摘要 ii Abstract iii Contents iv List of Figures vi Chapter 1 Introduction 1 1.1 Preliminaries and related work 1 1.2 An overview of the thesis 2 Chapter 2 Problem description and the algorithms 3 2.1 Formal definition of the problem 3 2.2 Preprocessing 4 2.3 Longest k-mismatch palindromic prefix 6 2.3.1 Reduction to persistent predecessor search problem 8 2.3.2 Reduction to orthogonal planar point location problem 8 2.3.3 Algorithm for vertical decomposition involving insertions only 10 2.3.4 Time and space complexities 14 2.4 Longest k-mismatch palindromic infix 15 2.5 Longest k-mismatch palindromic substring 17 Chapter 3 Conclusion 18 3.1 Future work 18 References 20 | - |
| dc.language.iso | en | - |
| dc.title | 近似迴文子序列查詢演算法 | zh_TW |
| dc.title | Internal Longest k-mismatch Palindrome Queries | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-1 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 王弘倫;吳彥緯 | zh_TW |
| dc.contributor.oralexamcommittee | Hung-Lung Wang;Yen-Wei Wu | en |
| dc.subject.keyword | 迴文,近似迴文,計算幾何,字串, | zh_TW |
| dc.subject.keyword | palindrome,approximate palindrome,computational geometry,string, | en |
| dc.relation.page | 21 | - |
| dc.identifier.doi | 10.6342/NTU202404555 | - |
| dc.rights.note | 未授權 | - |
| dc.date.accepted | 2024-11-07 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 資訊工程學系 | - |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-1.pdf 未授權公開取用 | 413.39 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。