做做下竟然要用到尋日果個data structure!
真不知是巧合還是甚麼
很正路的先compute S=A+B 的suffix array和計算height array
然後數法就是對於每一條在A開頭的suffix去數map到幾多條B開頭的, 分別向上和向下掃一次
所以就要用昨天的data structure去計算了, 因為LCP在SA中是decreasing的
題外話
我的O(N lg N lg N) 武器 run 了 34xx ms
但貼左個 O(N lg N) 的就變成 18xx ms了
No comments:
Post a Comment