AtCoder Beginner Contest 268 Ex - Taboo 解題心得 ( 題目 )
解題概念: AC自動機 (Aho-Corasick Automaton)
解題方法:這題的解題策略其實不難，主要是先推得出一個貪心的想法，只要找到完整的字串就把最後一格畫上*號，這樣greedy會是好的，而找字串的地方直接暴力或是用KMP的話複雜度不夠好(考慮到這題可能會有很多字串)，這裡可以使用 AC自動機 ，時間複雜度為 O(26*sum+N+sum)。
Java solution code:
https://wtools.io/paste-code/bEUb
文章標籤
全站熱搜
留言列表
