using System;

unsafe class Program
{
    static int kmp(char[] substr, char[] str)
    {
        int i, j, N, M;

        N = str.Length;
        M = substr.Length;

        int*[] d = new int*[M * sizeof(int)];
        *d[0] = 0;

        for (i = 0, j = 0; i < M; i++)
        {
            while (j > 0 && substr[j] != substr[i])
            {
                *d[j] = i - 1;
            }

            if (substr[j] == substr[i])
            {
                j++;
                *d[i] = j;
            }
        }

        for (i = 0, j = 0; i < N; i++)
        {
            while (j > 0 && substr[j] != str[i])
            {
                *d[j] = i - 1;
            }

            if (substr[j] == str[i])
            {
                j++;
            }

            if (j == M)
            {
                d = null;
                GC.Collect();
                return i - j + 1;
            }
        }

        d = null;
        GC.Collect();

        return -1;
    }

    static void Main()
    {
        char[] substr = "World".ToCharArray(),
            str = "Hello World!\r\n".ToCharArray();

        int pos = kmp(substr, str);
    }
}