String pattern matching with KMP

Build up a prefix table for pattern abcdabca

---

KMP method build up a prefix table for a particular pattern to reducing some initial checking.

Steps for build up a prefix table:

• create a 1D table size of pattern.length and fill the table with zeros

  a	b	c	d	a	b	c	a
  0	0	0	0	0	0	0	0

• create an index tracker for tracking the prefix and initialize with 0

• follow up this sudo code:

  • iterate start from 1:

  • if pattern[iterator index] matched with pattern[tracker index] then table[iterator index]=tracker+1 ,iterate+=1 and tracker+=1

  • else :

    • if tarcker is zero then iterate+=1 else tracker=table[tracker-1]

    /* tracker */
    int index = 0;

    for(int i=1; i<p_len; i++)
    {
        /* if this two index value matched-then both go for next */
        if(pattern[i] == pattern[index])
        {
            table[i] = index + 1;
            index++; i++;
        }
        else
        {
            /* for non-zero index-> go the previous matched index */
            if(index != 0)
                index = table[index-1];
            else
                i++;
        }
    }

---

How the table is building:

initial stage:

pattern table

0	1	2	3	4	5	6	7
a	b	c	d	a	b	c	a

prefix table

a	b	c	d	a	b	c	a
0	0	0	0	0	0	0	0

index = 0

iterate = 1

---

current index = 0
current iterate = 1

pattern[index] = a
pattern[iterate] = b

pattern[iterate] does not matched with pattern[index]
as index is zero so iterate = iterate + 1

next index = 0
next iterate = 2

current index = 0
current iterate = 2

pattern[index] = a
pattern[iterate] = c

pattern[iterate] does not matched with pattern[index]
as index is zero so iterate = iterate + 1

next index = 0
next iterate = 3

current index = 0
current iterate = 3

pattern[index] = a
pattern[iterate] = d

pattern[iterate] does not matched with pattern[index]
as index is zero so iterate = iterate + 1

next index = 0
next iterate = 4

current index = 0
current iterate = 4

pattern[index] = a
pattern[iterate] = a

pattern[iterate] matched with pattern[index]

table[iterate] = index + 1
iterate = iterate + 1
index = index + 1

next index = 1
next iterate = 5

update the table

a	b	c	d	a	b	c	a
0	0	0	0	1	0	0	0

---

current index = 1
current iterate = 5

pattern[index] = b
pattern[iterate] = b

pattern[iterate] matched with pattern[index]

table[iterate] = index + 1
iterate = iterate + 1 
index = index + 1

next index = 2
next iterate = 6

update the table

a	b	c	d	a	b	c	a
0	0	0	0	1	2	0	0

---

current index = 2
current iterate = 6

pattern[index] = c
pattern[iterate] = c

pattern[iterate] matched with pattern[index]

table[iterate] = index + 1
iterate = iterate + 1
index = index + 1

next index = 3
next iterate = 7

update the table

a	b	c	d	a	b	c	a
0	0	0	0	1	2	3	0

---

current index = 3
current iterate = 7

pattern[index] = d
pattern[iterate] = a

pattern[index] does not matched with pattern[iterate] 

As index is not zero so index = table[index-1] = table[2] = 0
No change in iterate

next index = 0
next iterate = 7

current index = 0
current iterate = 7

pattern[index] = a
pattern[iterate] a

pattern[index] matched with pattern[iterate]
table[iterate] = index + 1
index = index + 1
iterate = iterate + 1

END

update the table - the final look

a	b	c	d	a	b	c	a
0	0	0	0	1	2	3	1

---

Program Code