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
arrow
arrow
    文章標籤
    Java 程式設計 解題心得 自主學習 AtCoder Trie Aho-Corasick Automaton
    全站熱搜

    En Chi Tsung 發表在 痞客邦 留言(0) 人氣()