KMP - algorithm for string matching
complexity of compute prefix function O(m) ,where m is length of the pattern
complexity of KMP is O(n)
Reference-Coreman 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int pie[500];
char *pattern;
char *text;
int m;  //length is pattern
int n;  //length of text
void compute_prefix()
{
    cin>>pattern+1;
    cin>>text+1;
     m=strlen(pattern+1);
    int k=0;
    pie[1]=0;
    for(int q=2;q<=m;q++)
    {
        while(k>0&&pattern[k+1]!=pattern[q])
        {
            k=pie[k];
          
        }
        if(pattern[k+1]==pattern[q])
            k=k+1;
        pie[q]=k;

    }
}
void kmp_matching()
{

     compute_prefix();
     n=strlen(text+1);
     int q=0;
     for(int i=1;i<=n;i++)
     {
         while(q>0&&pattern[q+1]!=text[i])
         {
             q=pie[q];
         }
         if(pattern[q+1]==text[i])
             q=q+1;
         if(q==m)
         {
             printf("pattern occurs with shift %d\n",i-m);
             q=pie[q];
         }
     }

}

int main()
{

    pattern=new char[500];
    text=new char[1000];
        kmp_matching();
    return 0;
}