Algoritmy a datové struktury

int Naive(string text, string pattern)
{
    int n = text.Length;
    int m = pattern.Length;
    for (int i = 0; i < n - m + 1; i++)
    {
        // NB: Substring creates a new string but let's not worry about that.
        if (text.Substring(i, m) == pattern)
        {
            return i;
        }
    }
    return -1;
}

int KarpRabin(string text, string pattern)
{
    int n = text.Length;
    int m = pattern.Length;
    int patternHash = pattern.GetHash();
    for (int i = 0; i < n - m + 1; i++)
    {
        // NB: Assume that `GetHash` is a rolling hash, even though in .NET it's not.
        if (text.Substring(i, m).GetHash() == patternHash)
        {
            if (text.Substring(i, m) == pattern)
            {
                return i;
            }
        }
    }
    return -1;
}

int[,] CreateAutomaton(string pattern)
{
    int m = pattern.Length;
    // NB: Assumes that the alphabet is ASCII.
    int[,] automaton = new int[m + 1, 256];
    for (int q = 0; q <= m; q++)
    {
        for (int c = 0; c < 256; c++)
        {
            int k = Math.Min(m + 1, q + 2);
            do
            {
                k--;
            }
            while (!pattern.Substring(0, q).Equals(pattern.Substring(0, k) + (char)c));
            automaton[q, c] = k;
        }
    }
    return automaton;
}

int FiniteAutomaton(string text, string pattern)
{
    int n = text.Length;
    int m = pattern.Length;
    int[,] automaton = CreateAutomaton(pattern);
    int q = 0;
    for (int i = 0; i < n; i++)
    {
        q = automaton[q, text[i]];
        if (q == m)
        {
            return i - m + 1;
        }
    }
    return -1;
}

/// <summary>
/// Computes the longest proper prefix of P[0..i]
/// that is also a suffix of P[0..i].
/// </summary>
int[] ComputeFailure(string pattern)
{
    int m = pattern.Length;
    int[] fail = new int[m];
    int j = 0;
    for (int i = 1; i < m; i++)
    {
        while (j >= 0 && pattern[j] != pattern[i])
        {
            j = fail[j];
        }

        // If comparison at i fails,
        // return to j as the new starting point.
        fail[i] = j;

        j++;
    }
    return fail;
}

int KnuthMorrisPratt(string text, string pattern)
{
    int[] fail = ComputeFailure(pattern);
    int n = text.Length;
    int m = pattern.Length;
    // NB: I index from 0 here. Although I use 1..n in the text.
    int i = 0;
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        while (j >= 0 && text[i] != pattern[j])
        {
            /*
                There can be at most n-1 failed comparisons
                since the number of times we decrease j cannot
                exceed the number of times we increment i.
            */
            j = fail[j];
        }

        j++;
        if (j == m)
        {
            return i - m;
        }
    }
    return -1;
}