Exercises 32.4-6 * Answer add

[Akasakar]

Give an efficient algorithm for computing the transition function δ for the string-matching automaton corresponding to a given pattern P. Your algorithm should run in time O(m |Σ|). (Hint: Prove that δ(q, a) = δ(π[q], a) if q = m or P[q + 1] ≠ a.)

You can find answer on 根据前缀函数构建一个自动机

void compute_transition_function(char P[], vector<char> Sigma)
{
    int m = strlen(P);
    vector<int> pi = compute_prefix_function(P);
    for(int q = 0; q <= m; q++)
        for(int i = 0; i < Sigma.size(); i++)
        {
            char& a = Sigma[i];
            //int k = min(m, q + 1);
            //while(!is_suffix(P, k, q, a)) k--;
            int k = q;
            while(k > 0 && P[k] != a) k = pi[k - 1];
            if(P[k] == a) k++;
            delta(q, a) = k;
        }
}