dipu-bd
6/29/2017 - 7:29 PM

## Implementation of KMP. Complexity O(n+m)

Implementation of KMP. Complexity O(n+m)

``````/*==================================
Title: Implementation of KMP Algorithm
Complexity: O(n)
Author : Sudipto Chandra
===================================*/
#include <bits/stdc++.h>
using namespace std;

const int SIZ = 100050;

int n, m;
char T[SIZ]; // given Text
char P[SIZ]; // Pattern to search
int pi[SIZ]; // LPS of pattern array. size=m
int lps[SIZ]; // LPS of pattern on text. size=n

// Build LPS array of the Pattern. Complexity: O(m)
// LPS[i] = Longest Prefix that is also a Suffix of P[0...i]
void computePrefix(int m)
{
pi[0] = 0;
int q = 0;
for(int i = 1; i < m; ++i)
{
while(q > 0 && P[q] != P[i])
{
q = pi[q - 1];
}

if(P[q] == P[i])
{
q++;
}
pi[i] = q;
}
}

// Find longest common prefix of the pattern
// occurs in the text. Complexity: O(n + m)
void KMP()
{
n = strlen(T);
m = strlen(P);

computePrefix(m);

int q = 0;
for(int i = 0; i < n; ++i)
{
while(q > 0 && P[q] != T[i])
{
q = pi[q - 1];
}
if(P[q] == T[i])
{
q++;
}
lps[i] = q;
}
}

void SHOW()
{
vector<int> gap;

printf("\n      ");
for(int i = 0; i < n; ++i)
{
printf("%3c", T[i]);
}
printf("\nlps = ");
for(int i = 0; i < n; ++i)
{
printf("%3d", lps[i]);
if(lps[i] == m) gap.push_back(i - m + 1);
}
printf("\n------");
for(int i = 0; i < n; ++i)
{
printf("---");
}

if(gap.empty())
{
return;
}

for(int k = 0; k < gap.size(); ++k)
{
int x = gap[k];

printf("\n[@%3d]", x);
if(x) printf("%*c", x * 3, ' ');
for(int i = 0; i < m; ++i)
{
printf("%3c", P[i]);
}
printf("\n%*c", x * 3 + 6, ' ');
for(int i = 0; i < m; ++i)
{
printf("%3d", pi[i]);
}
printf("\n------");
for(int i = 0; i < n; ++i)
{
printf("---");
}
}

puts("");
}

void RUN()
{
printf("Text: ");
gets(T);
for(printf("\nPattern: "); gets(P); printf("\nPattern: "))
{
KMP();
SHOW();
}
}

int main()
{
RUN();

return 0;
}
``````