private int[] calculatePrefSuffArray(String pattern) {
    char patternArray[] = pattern.toCharArray();
    int tab[] = new int[pattern.length()];
    tab[0] = 0;
    int t = tab[0];
    for (int i = 1; i < pattern.length(); i++) { // t = tab[i-1]
        while(t >0 && patternArray[i] != patternArray[t] ) {
            t = tab[t-1];
        }
        if(patternArray[i] == patternArray[t]) t++;
        tab[i] = t;
    }
    return tab;
}

#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

  main()
  {
    ofstream myfile("inputtext.txt");
    char *intxt="abcd"; // I wish the sample text to contain only these alphabets
    long int i=0;
    char* txt = new char[10000000];
    while(i<10000000)
       {
       txt[i]=intxt[(rand()%4)];
       i++;
       }
   myfile<<txt;
   myfile.close();
  }

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

 void prefix_fn(int* p, char* s)
 {
 s--;
 p--;
 int i,k=0;
   p[1]=0;
   for(i=2;i<=7;i++)
   {
     while ((k>0)&&(s[k+1]!=s[i]))
         k=p[k];
     if (s[k+1]==s[i])
         k++;
     p[i]=k;
   }
 }
main()
{
int i,k;
int *p= new int[7];
char* txt=new char[10000000];
ifstream myfile("inputtext.txt");
myfile.seekg(0,ios::beg);

myfile.read(txt,10000000);
myfile.close();
char *s="abdcbab";
cout<<"Prefix Table"<<endl;
prefix_fn(p,s);
p--; // This helps to start indexing from 1, just for me to avoid confusion
s--; // Similar objective as stated above.
   for(int i=1;i<=7;i++)
      cout<<p[i]<<endl;
txt--;
k=0;
  for(i=1;i<=10000000;i++)
    {
       while(k>0 && s[k+1]!=txt[i])
           {
            k=p[k];
           }
       if(s[k+1]==txt[i])
           {
            k=k+1;
           }
        if(k==7)
           {
            cout<<"Match found at position : "<<i-6<<endl;
            k=p[k];
           }
    }
p++;
delete[] p;
txt++;
delete[] txt; //deleting the memory allocated.
}

[0  0  0  0  1  2  3  0  1  2  0  1  2  3  0  1  2  3  0  1  2  0  0]

[-1  0  0  0  1  2  3  0  1  2  0  1  2  3  0  1  2  3  0  1  2  0  0 ]

tab[0] = 0;
int t = tab[0];

tab[0] = -1;
tab[1] = 0;
int t = tab[1];

private boolean search(String string, String word, int[] table) {
    int m = 0, i = 0;
    while ((m + i) < string.length()) {
        if (word.charAt(i) == string.charAt(m + i)) {
            if (i == word.length() - 1) {
                return true;
            }
            i++;
        } else {
            if (table[i] > -1) {
                m = m + i - table[i];
                i = table[i];
            } else {
                i = 0;
                m++;
            }
        }
    }
    return false;
}

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """

        if not needle:
            return 0

        q = 0
        preList = self.calPre(needle)
        # print preList
        for i in xrange(len(haystack)):
            # print needle[q], haystack[i], i
            while q>0 and needle[q] != haystack[i]:  # 加入循环，让累加子串充分比较，直到q变成0，防止haystack中有元素未参与可能相等的比较
                q = preList[q]
            if needle[q] == haystack[i]:
                q += 1
            if q == len(needle):
                return i - len(needle) + 1    # 比较完毕
        return -1

    def calPre(self, s):
        preList = [0, 0]
        i = 1
        j = 0
        while i < len(s):
            if s[i] == s[j]:     # 进行子串累加匹配
                preList.append(j+1)
                i += 1
                j += 1
            elif s[i] == s[0]:  # 重新开始子串匹配
                j = 0
            else:                  # 无法匹配
                preList.append(0)
                i += 1
                j = 0
        return preList