String pattern matching with transition table (finite automata)

Example: Build a transition table for this pattern: ababaca

Here set of alphabet for this pattern: {a, b, c}

---

Steps for build up a transition table:

• create a table of format [length of pattern][number of alphabet]

• initialize row[0] that means state[0] with zeros and update table[0][pattern first alphabet] = 1

• use a row tracker for track the transition from previous one. Initially tracker = 0 which indicate that state[1] will copy the state[0] data

• after copy from transition data from a previous state then update table[currrent state][current pattern alphabet] = current state + 1; which simply indicate that with this alphabet go to next state

• to update the tracker for next state : tracker = table[current tracker value][current alphabet]

• tracker will update till a state can reach the final state with an alphabet or simply while row < length of pattern.

    // tracker index for row value copy
    int track = 0;
    // iteration index
    int row, col;

    // for first row of the table
    for(col=0; col<CHARACTERS; col++)
        tabl[0][col] = 0;
    // update the next index of first character from the pattern
    tabl[0][patt[0]] = 1;

    for(row=1; row<=patt_len; row++)
    {
        // copy row value from tracker row
        for(col=0; col<CHARACTERS; col++)
            tabl[row][col] = tabl[track][col];
        // set next state for current index character
        tabl[row][patt[row]] = row+1;

        // last row will copy the first row value for re-checking
        if(row<patt_len)
            track = tabl[track][patt[row]];
    }

---