Still AC automata

      I still watch it today AC automata , It's very difficult. , The subject is difficult to understand , I saw AC Different applications of automata , To sum up ：

      The first is the most basic application ： Pattern matching problem , For example, count how many given words are contained in the text string , The method is to insert the words to be matched into a tree in turn , Reuse AC The method of automata to match the text string . This kind of problem , Just focus on the relationship between text string and pattern string , No other knowledge has been involved .

        Then with DP Combination , The difficulty comes up , Today I mainly looked at probability DP+AC Automata and pressure DP+AC automata , This kind of problem is mainly to find the state transition equation, and then in AC Automata is implemented on this data structure , Strictly speaking , This kind of problem still belongs to DP Special . But it's about AC Automata DP The problem of state transition equation is really hard to think about , Some can't even understand the problem solution , The equation is cleverly constructed .

      Watch it again tomorrow .