Monday, January 25, 2016

Pattern Matching KMP Algorithm

#include <iostream>
#include <string>

using namespace std;

int main() {
string text = "abxabcabcaby";
string pattern = "abcaby";

int n  = text.length();
int m  = pattern.length();
int j = 0;

int * prefix = new int [m];
prefix [0] = 0;

for (int i = 1; i< m; i++) {
if (pattern[i] == pattern[j]) {
prefix[i] = j + 1;
j++;
} else if (prefix[i-1] == 0){
continue;
} else {
j = prefix[i - 1];
}
}

for (int i = 0; i< m; i++) {
cout<<prefix[i];
}

int i = 0;
j = 0;

while(i < n) {

if (pattern[j] == text[i]) {
j++;
i++;
}

if (j == m) {
printf("Found pattern at index %d \n", i-j);
        j = prefix[j-1];
} else if (i < n && pattern[j] != text[i]){
if (j != 0)
          j = prefix[j-1];
        else
          i = i+1;
}
}

delete (prefix);
return 0;
}

No comments: