//########## METHOD 3: with Array ##########

using System;

​

string T = "abcabaabcabac";

string P = "abaa";

​

int[] MatchIndex = new int[T.Length];

​

for (int i = 0; i < T.Length - P.Length + 1; i++)

{

    MatchIndex[i] = 0;

    if (T[i] == P[0] && T[i + P.Length - 1] == P[^1])

        MatchIndex[i] = 1;

}

​

for (int j = 0; j < MatchIndex.Length; j++)

{

    if (MatchIndex[j] == 1)

        MatchIndex[j] = CheckMatch(j, 1, P.Length - 2);

}

​

for (int k = 0; k < MatchIndex.Length; k++)

{

    if (MatchIndex[k] == 1)

        Console.WriteLine(k.ToString());

}

​

int CheckMatch(int index, int iStart, int iEnd)

{

    if (iStart >= iEnd) 

        return MatchIndex[index];

    if (T[index + iStart] != P[iStart] || T[index + P.Length - iEnd] != P[^iEnd]) return 0;

    return CheckMatch(index, ++iStart, --iEnd);

}