題目連結: http://ppt.cc/avSY
題意:
給予兩個由 R, G, B 所組成的字串 s (|s| <= 10^6) 和 t (|t| <= 10^6)
一開始有兩個人分別位在 s[1] 和 t[1] 上 (index 為 1-base)
現在可以對這兩個人下指令,比如 「站在 R 上的人前進一格」
此時如果 s[1] = R,則第一個人必須走到 s[2],站在 t 上的人亦同
所以如果兩個人所站的 s[i] 和 t[j] 顏色一樣,則下達該顏色會讓兩個人同時前進
如果有某一個人已經站在 sequence 的尾巴 (s[length(s)] 或 t[length(t)])
則不能下 s[length(s)] 或 t[length(t)] 那格的顏色
也就是不能下會讓某一個人走出自己所處 sequence 的命令
現在定義一個狀態 (i, j) 是 reachable 為
存在一個命令 sequence I,使從 s[1] 和 t[1] 出發,按照 I 的命令走完之後
可以使兩人最後分別停在 s[i] 和 t[j]
否則為 unreachable
問 reachable 的狀態總數