Problem
KMP Search
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : KMP Search
Created Date : 04-10-2013
Last Modified :
============================================================================
*/
/*
algorithm kmp_search:
input:
an array of characters, S (the text to be searched)
an array of characters, W (the word sought)
output:
an integer (the zero-based position in S at which W is found)
define variables:
an integer, m ← 0 (the beginning of the current match in S)
an integer, i ← 0 (the position of the current character in W)
an array of integers, T (the table, computed elsewhere)
while m + i < length(S) do
if W[i] = S[m + i] then
if i = length(W) - 1 then
return m
let i ← i + 1
else
let m ← m + i - T[i]
if T[i] > -1 then
let i ← T[i]
else
let i ← 0
(if we reach here, we have searched all of S unsuccessfully)
return the length of -1
*/
#include <iostream>
#include <cassert>
using namespace std;
int KMPSearch(string S, string W)
{
int m(0);
int i(0);
int T(-1);
while(m + i < S.size()){
if(W[i] == S[m + i]){
if(T == -1 && i != 0 && W[0] == S[m + i]){
T = i;
}
if(i == W.size() - 1){
return m;
}
i ++;
}
else{
m += (T == -1) ? i + 1 : T;
T = -1;
i = 0;
}
}
return -1;
}
int main(int argc, char* argv[])
{
cout << KMPSearch("abcde", "accf") << endl;
cout << KMPSearch("abcde", "bed") << endl;
cout << KMPSearch("abced", "bce") << endl;
cout << KMPSearch("abced", "ced") << endl;
cout << KMPSearch("abced", "a") << endl;
return 0;
}
Output
-1
-1
1
2
0
Press any key to continue . . .