大衞的筆記

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二上統計學重點整理
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是觀看影片心得後的筆記，老師上課可能不太適用會忘記抄到

題目大意：

生物學家們要透過 DNA bases(A,C,G,T) 在人類的 DNA 片段中找出最長重複的子字串並且告訴生物學家出現幾遍。

Suffix Tree 介紹

Suffix Tree 是字典樹(Trie) 的延伸，透過對一字串的所有後綴去建構樹，是一個能解決許多字串特定問題的資料結構。

以下是 Suffix Tree 能解決的問題：

• 尋找 A 字串是否在字串 B 中
• 找出 B 在 A 字串重複的次數
• 最長共同子字串

簡單來說 Suffix Tree 是將字串的所有後綴建構成 Trie，再將其壓縮(沒有分支的節點都放在同個節點)。

建立 Suffix Tree 的時間複雜度為 \(O(n)\)，使用 Ukkonen Algorithm
通常建構 Suffix Tree 有兩種方法，一種時間複雜度為 \(O(n)\)，另一種為 \(O(n^2)\)，這裡只介紹普遍比賽會經用的演算法(Ukkonen Algorithm)

此文章跳開蠻多證明與理論，如果想要知道可再從下方參考連結點選即可

題目大意：

有一串項鍊由於線繩脆弱，可能會在最重與最輕的珠子的中間因為重力關係而導致繩線裂開，這些珠子的權重分別用英文字母表示，由於這些英文字母是循環的，給你一組字串試問怎麼樣找出此字串字典序最小的循環字串。

循環字串：假如字串有 “abc”，那則會 abcabcabc… 不斷循環下去，但總長度必定為原本字串長度，類似於項鍊。

Suffix Automaton 介紹

Suffix Automaton，簡稱 SAM，(以下內文都簡稱 SAM)，是一個能解決許多字串特定問題的資料結構。

只要關於這兩個字串問題都可以使用 \(O(n)\) 時間複雜度解決：

• 在另一個字串中查詢另一個字串的所有出現位置
• 計算此字串中裡面有多少不同的子字串

簡單來說 SAM 可以理解成字串壓縮，一個 SAM 最多只會有 \(2n-1\) 個節點與 \(3n-4\) 個轉移邊。

建立 SAM 的時間複雜度為 \(O(n)\)

此文章跳開蠻多理論與證明，如果想要知道可再從下方參考連結點選即可

文章大意：

如果發現最後一次的 commit 並不是最好的版本，想要回去之前的版本要如何做比較好？

僅此紀錄大衛大一下至大二上參加惠特科技產學合作心得。
「紀錄每個時刻，讓未來的自己不遺忘過去的自己」
只有自己才能體會自己的過去
謝謝惠特副總經理與洪揮霖老師與官齊笎陪伴我成長。

筆記說明

此筆記用途在於台北科技大學資訊與財金管理系大二上統計學重點整理
並非所有人都適用，部分對我而言稍加容易的內容並不會寫在此內。
這是觀看影片心得後的筆記，老師上課可能不太適用會忘記抄到

Radix Sort 介紹與應用

Radix Sort 與我們一般常見的比較排序不同，採用分配式排序法(透過特定方式將值分別放入不同的 array)，Radix Sort 是特殊的整數排序法，Radix Sort 是根據每一位的數值放入相對應的 index。

時間複雜度為 \(O(dn)\)

題目大意：

給你兩組字串，想請你找出裡面其中最長的共同子字串，如果有複數最長的子字串則透過字典序輸出。

注意：這題的輸出格式有特別要求