#include<iostream>
#include<string.h>
using namespace std;

void findPrefix(string pattern, int m, int prefArray[])
{
   int i = 0;
   prefArray[0] = 0;                        //first place is always 0 as no prefix

   for(int j = 1; j<m; j++)
    {
      if(pattern[j] == pattern[i])
      {
         i++;
         prefArray[j] = i;
      }
      else
      {
         if(i != 0)
         {
            i = prefArray[i - 1];
            j--;                            //decrease i to avoid effect of increasing after iteration
         }
         else
            prefArray[j] = 0;
      }
   }
   printf("\n");
   for(i=0;i<m;i++)
    printf(" %d ", prefArray[i]);
}

void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc)
{
   int n, m, i = 0, j = 0;
   n = mainString.size();
   m = pattern.size();
   int prefixArray[m];                      //prefix array as same size of pattern
   findPrefix(pattern, m, prefixArray);
   loc = 0;
   while(i < n)
   {
      if(mainString[i] == pattern[j])
      {
         i++; j++;
      }
      if(j == m)
      {
         locArray[loc] = i-j;               //item found at i-j position.
         loc++;
         j = prefixArray[j-1];              //get the prefix LENGTH from array
      }
      else if(i < n && pattern[j] != mainString[i])
      {
         if(j != 0)
            j = prefixArray[j-1];
         else
            i++;
      }
   }
}

int main()
{
   char str[100], patt[100];
   int locationArray[100], index;

   cout << "\nEnter the string: ";
   gets(str);

   cout << "\nEnter the patttern: ";
   gets(patt);

   kmpPattSearch(str, patt, locationArray, index);

   for(int i = 0; i<index; i++)
   {
      cout << "Pattern found at location: " <<locationArray[i] << endl;
   }
}