# Lecture 5

## Reference

[Lec05 資料結構 第三週課程](https://youtu.be/cgaPEsMJkSc)

## Notes

### Sparse Matrix (00:10)

- 左邊是一個sparse matrix，因為大部分的值是0，所以可以用其他資料結構來存


- 將sparse matrix中的值及所在的行列依照<row, col, value>的格式記下來
- 注意行列有排序


- Transpose (轉置):
- 方法一：直接把row/col交換，交換完再調整這個值所在的位置，例如下方轉置完的(1, 1, 11)應該要往上移


- 程式碼實現：
- 前三行：將行列最大值交換、值的個數不變
- 最外面的if：如果矩陣有元素的話，執行裡面的兩個for迴圈
- 外面的for迴圈是依照原本的Cols去排序，因為轉置之後新的row就變成col了
- 裡面的for迴圈會檢查原本的矩陣中所有terms的col，如果是c的話，就把元素擺進去，然後CurrentB++，找轉置後的矩陣中，下一個位置要擺的term
- Time Complexity: $O(terms*cols)$


- 方法一的問題是對於不同的cols，都要檢查一遍所有的terms有沒有符合
- 方法二：多利用一組資料，資料會記載原本的matrix中，每個不同的row出現的次數，還有這個row出現的起始位置，index就是row的值


- 程式碼實現：
- if判斷式之前的程式與方法一大同小異，只是多了Rows跟RowStart
- if判斷式判斷matrix不是空的
- 剩下三個for迴圈在計算RowSize跟RowStart


- 程式碼實現 (cont.)：
- for迴圈對於每個Terms做轉置
- int j 代表的是現在這個term應該要丟到的新矩陣的對應位置
- 接下來三行就是把單個term的行列互換、值直接丟過去新的矩陣
- RowStart要++這樣才不會丟到同一個位置
- 綜合上述，時間複雜度大約是$O(row*column)$


### Matrix Multiplication (29:12)

$$
result_{ij} = \sum_{k=0}^{n-1}a_{ik}b_{kj}
$$

### Arrays in Memory (30:09)

- Row Major : 記憶體會先把一整列的值放完，再放下一列
- 延伸成多維矩陣，記憶體會以最高維度的資料作為擺放方式


### String (33:21)

- 可以當作字元陣列 (character array)
- 常見的字串處理包含：字串比對、串接、複製、插入等

### String Matching (36:36)

- P : Pattern; T : Text; m : Length of P; n : Length of T
- 目標找出P出現在T中的起始位置
- 最簡單的方式就是從T的第一個位置開始慢慢比對，如果比錯了就把pattern位移一個字元，然後再比對一次


### KMP Method (52:55)

- 主要精神：比錯的時候，可不可以一次位移多個字元
- 例子：
- 比對到第四個位置時，Pattern直接位移三格


- 例子：
- 第七個位置不一樣，把P的粉紅色區塊跟T的粉紅色對齊，這時候移了五格
- 接下來比對T的第七個位置及P的第二個位置


- 例子：
- 同樣比到不一樣的位置時，根據粉紅色的區塊位移


- KMP Algorithm
- 如果比對到不相同時，根據Failure function決定要移多少格
- 粉紅色區塊代表這兩段的字串長得一樣，Failure function是在算粉紅色區塊的最大長度k
- 兩段粉紅色區塊有overlap沒關係


- 計算Failure function的例子(注意這裡index是從1開始算)：
1. 第一個位置沒得比較，Failure function[1]為0
2. 第二個位置p[2]=’b’，Failure function[2]為0
3. 第三個位置p[3]=’a’，Failure function[3]為1，因為p[3]==p[1]
4. 第四個位置p[4]=’b’，Failure function[4]為2，因為[p[3], p[4]]==[p[1], p[2]]，也就是’ab’
5. 其他同理



- 如果S[i]跟P[j]不一樣，下次就比對S[i]跟P[f(j-1)+1]，等同於前面所講的位移


- 更多例子：
1. 一開始比對S[1]與P[1]，不一樣，所以位移一格
2. 比對S[2]與P[1]，一樣


1. 比對S[3]與P[2]，不一樣，看P[2-1]的Failure function為0，因此比對S[3]與P[1]，還是不一樣，因此位移一格，總共位移兩格
2. 比對S[4]與P[1]，不一樣，位移一格
3. 比對S[5]與P[1]，一樣


1. 比對S[6]與P[2]，一樣
2. 比對S[7]與P[3]，一樣
3. 比對S[8]與P[4]，一樣


1. 比對S[9]與P[5]，還是一樣
2. 比對S[10]與P[6]，不一樣了，看P[6-1]的Failure function為3，因此比對S[10]與P[4]，現在一樣了
3. 繼續比對S[11]與P[5]，一樣


1. 比對S[12]與P[6]，一樣
2. 比對S[13]與P[7]，一樣，P完全一樣，程式結束


- Time complexity : $O(m+n)$
- $m:$ P的長度，計算Failure function
- $n:$ S的長度