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]];
    }

---

How to the transition table is building:

state	a	b	c	pattern	next row tracker
0	1	0	0	a	initialize with 0
1	1	0 > 1+1=2	0	b	table[0][b] = 0
2	1 > 2+1=3	0	0	a	table[0][a] = 1
3	1	2 > 3+1=4	0	b	table[1][b] = 2
4	3 > 4+1=5	0	0	a	table[2][a] = 3
5	1	4	0 > 5+1=6	c	table[3][c] = 0
6	1 > 6+1=7	0	0	a	finish line: no update: 0
7	1	0	0	next iteration start	based on next iteration

---

Final Table:

state	a	b	c	pattern
0	1	0	0	a
1	1	2	0	b
2	3	0	0	a
3	1	4	0	b
4	5	0	0	a
5	1	4	6	c
6	7	0	0	a
7	1	0	0	next iteration start

---

text: ababacababaca :

There will 2 match for this text for this above pattern.

index=0 = ababacababaca

index=6 = ababacababaca

    for(index=0; index<text_len; index++)
    {
        // update the matched pattern length from transition table
        len = tabl[len][text[index]];
        // whether matched pattern length equal with pattern length then match found
        if(len == patt_len)
        {
            // print out the index from where match started
            printf("Pattern match at index: %d\n",index-(patt_len-1));
            // change the flag
            flag = 1;
        }
    }

---

Program Code