pattern searching algorithm KMP, just the precomputer part for now.

kmp.cpp

#include <iostream>
#include <fstream>
#include <string.h>

#define Nmax 101

using namespace std;

ifstream f("date.in");

char t[Nmax], p[Nmax]; // t = text, p = pattern
int lps[Nmax]; //longest prefix suffix

/*
 * Creates the LPS table that finds the 'patterns in patterns'
 * If matched, we go further with the compare
 * If not, we check to see if the len is > 0
 *                                    if so, we stepback our len so we can take a lookback at the string
 *                                    if not, we obviously have no patters, so we put 0 at the current index
 */
void computeLPS(char* p, int M) {

    int len = 0; // length of previous lps
    lps[0] = 0;

    int i = 1;

    while (i < M) {

        if (p[i] == p[len]) {
            len ++;
            lps[i] = len;
            i ++;
        }
        else { // p[i] != p[len]
            if (len != 0) {
                len = lps[len - 1]; // stepback
            }
            else { // len == 0
                lps[i] = 0;
                i ++;
            }

        }
    }

}
int main()
{
    f.get(t, Nmax);
    f.get();
    f.get(p, Nmax);

    int M = strlen(p);

    computeLPS(p, M);

    for (int i = 0 ; i < M ; i ++)
        cout << lps[i] << " ";


    return 0;
}