大衞的筆記

Suffix Array 介紹

對某一字串的所有後綴進行字典排序，常用於全文索引、數據壓縮算法與生物資訊學。
這裡介紹的演算法寫法時間複雜度為 \(O(n \log n)\)

Suffix Array 原理

Suffix Array 主要是用 \(sa\) and \(rk\) 這兩個陣列組合而成。
且滿足此性質 \(sa[rk[i]] = rk[sa[i]] = i \)

Suffix Array 圖示說明：

QUESTION 1: sa (suffix array) 用途是甚麼呢？

\(sa[i]\) 表示此字串所有後綴排序後第 i 大的 index。

QUESTION 2: rk (rank array) 用途是甚麼呢？

\(rk[i]\) 表示此字串所有後綴排序後，字串中 index 後綴的排名。

QUESTION 3: 甚麼是所有後綴？

從第 i 個字元開始到最後一個字元的字串，i 的範圍是 string[0] ~ string.length()
所有後綴舉例如下，舉例單字為 apple：

• apple
• pple
• ple
• le
• e

閱讀更多...

筆記說明

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

閱讀更多...

題目大意：

有 X 的倉庫需要有人看守，每個人可以看守多個倉庫，但一個倉庫只能被一人看守，看守的規定如下：
每位看守人員的能力值與報酬相同
如果要讓一看守人員看多個倉庫則其能力值會依照此公式下降 \( \text{倉庫安全值} = \text{看守人員能力值} / \text{倉庫數量} \)，有小數點時取整數。
目標是要讓我們花費在看守人員的報酬最低並讓倉庫的安全值最高。

閱讀更多...

說明

記錄我在 2020/09/20 跟參加ICPC 競賽的隊友去餐廳吃飯紀錄
謝謝學長(風平) and 學弟(漢軒) 陪我參加這場比賽
沒有它們我根本甚麼都沒辦法完成，有他們我才有機會去嘗試夢想

閱讀更多...

僅此紀錄 2020/10/07 2020 ICPC Asia Taiwan Online Programming Contest 心得
「紀錄每個時刻，讓未來的自己不遺忘過去的自己」
只有自己才能體會自己的過去
僅只有 30th，還需要努力

閱讀更多...

使用 Hexo or Markdown 插入影片：

此文章教學如何用 Hexo or Markdown 中放入 youtube 影片

閱讀更多...

僅此紀錄 2020/10/09 109年度全國大專電腦軟體設計決賽心得。
「紀錄每個時刻，讓未來的自己不遺忘過去的自己」
只有自己才能體會自己的過去
僅只有 34th，還需要努力

閱讀更多...

題目大意：

給你一組電話號碼，不超過 10 位數，如果這一組的電話號碼內只要有一個電話號碼是另外一個電話號碼的前綴就輸出 “NO”，否則就輸出 “YES”

閱讀更多...

導讀

紀錄 2021 參加 110年度全國大專電腦軟體設計初賽

這次比賽前夕大家都比較趕，來不及複習很多 NCPC 初賽的題目，只有寫一次考古題就上戰場了

由於這次疫情關係，因此比賽改成用遠距的方式進行，稍微變得麻煩一些。
要跟教授討論出電腦教室辦公室位置，還有負責來幫忙監考我們。

總之來來回回的確認後，終於搞定了XD。

閱讀更多...

筆記說明

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

閱讀更多...