UVa11019 - Matrix Matcher

出處：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1960

解題策略：Aho–Corasick (AC)自動機

以下為本題的測試資料。

3 3

abc

bcd

cde

2 2

bc

cd

假設以下為陣列B，

B = [ bc

cd ]

使用陣列B的每一列建立自動機，是否為單字節點val，紀錄陣列B的每一列所在列數，可能有資料重複的列，所以使用vector紀錄多個列編號

假設以下為陣列A，

A = [ abc

bcd

cde ]

使用陣列A每一列輸入自動機，找到是否有單字節點，更新num[r][c]

找出bc在[ abc 出現的位置的num遞增1 [ 0 1 0

bcd 1 0 0

cde ] 0 0 0 ]

找出cd在[ abc 出現的位置的num遞增1 [ 0 2 0

bcd 2 0 0

cde ] 0 0 0 ]

計算出陣列num為陣列B的列數就是答案。