USACO DEC10 Threatening Letter

這是 USACO DEC10 GOLD division 的題目, 據說提交率/通過率很低
不過說穿了其實不難, 只是看對 Suffix Array 的運用是否熟練

題目大意是, 給出兩條 string A, B
現在可以不斷 copy 出 A 的一段 substring, 問最少要 copy 多少次去砌出 B
N ≤ 50000

首先想到的是很 greedy 地砌出 B, 即在 A 中選出和 B 的 prefix 有最長 common prefix 的suffix
所以就要用 suffix array
題解 suggest 了兩種做法

1. 設 S = A+B, 對 S 做 suffix array, 然後每次在 S 中 process
2. 對 B 做 suffix array, 然後不斷做 binary search

由於我覺得方法 2 好像在 worst case 中會達到 O(N² lg N), 所以很理所當然的用了方法1
每次找出 B 由 current 開始的 prefix 與 A 的 suffix 中最長 LCA 的一條
即是在 SA[] 中, 分別向上和向下找出第一條在 A 開頭的suffix

版本1 我是真的向上下掃一次的, 其實理論上應該會去到 O(N²), 不過還是水過了
版本2 對每條在A開始的 suffix 中向上下掃, O(N) preprocess (case 10 run 了 300ms)