using System;

using System.Collections.Generic;

using System.Linq;

using Xunit;

public class Program

{

    public static void Main()

    {

        //There are many algorithms to find pattern and search in strings

        //Boyer-Moore, Rabin-Karp, Knuth-Morris-Pratt, SuffixTree & so on

        //Here is just an example of using KMP Search, probably not the best one.

        string text = "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=";

        Dictionary<string, int> patterns = PatternDiscovery(text, 3);

​

        foreach (var item in patterns)

        {

            Console.WriteLine($"'{item.Key}': {item.Value}");

        }

    }

    private static Dictionary<string, int> PatternDiscovery(string text, int patternLength)

    {

        Dictionary<string, int> patterns = new Dictionary<string, int>();

​

        for (int i = 0; i < text.Length - patternLength; i++)

        {

            FindPattern(text, text.Substring(i, patternLength), patterns);

        }

​

        return patterns;

​

    }

​

    private static void FindPattern(string text, string pattern, Dictionary<string, int> patterns)

    {

        if (patterns.ContainsKey(pattern))

            return;

​

        ISearch kmpSearch = new KnuthMorrisPratt();

        List<int> searchResult = kmpSearch.Search(text, pattern)?.ToList();

​

        if (searchResult != null && searchResult.Any() && searchResult.Count > 1)

            patterns.Add(pattern, searchResult.Count);

    }

}

​

public interface ISearch

{

    IEnumerable<int> Search(string text, string pattern);

}

​

​

public class KnuthMorrisPratt : ISearch

{

    public IEnumerable<int> Search(string text, string pattern)

    {

        int textLength = text.Length;

        int patternLength = pattern.Length;

​

        if (textLength < patternLength)

            return null;

​

        if (textLength == patternLength && text == pattern)

            return new List<int>() { 0 };

        if (patternLength == 0)

            return new List<int>() { 0 };

​

        int[] lpsArray = new int[patternLength];

        List<int> matchedIndex = new List<int>();

​

        LongestPrefixSuffix(pattern, ref lpsArray);

​

        int textIndex = 0;

        int patternIndex = 0;

​

        while (textIndex < textLength)

        {

            if (text[textIndex] == pattern[patternIndex])

            {

                textIndex++;

                patternIndex++;

            }

​

            // match found at i-j

            if (patternIndex == patternLength)

            {

                matchedIndex.Add(textIndex - patternIndex);

                //Console.WriteLine((textIndex - patternIndex).ToString());

                patternIndex = lpsArray[patternIndex - 1];

            }

            else if (textIndex < textLength && text[textIndex] != pattern[patternIndex])

            {

                if (patternIndex != 0)

                {

                    patternIndex = lpsArray[patternIndex - 1];

                }

                else

                {

                    textIndex++;

                }

            }

        }

​

        return matchedIndex;

    }

​

    private void LongestPrefixSuffix(string pattern, ref int[] lpsArray)

    {

        int patternLength = pattern.Length;

        int len = 0;

        lpsArray[0] = 0;

        int patternIndex = 1;

​

        while (patternIndex < patternLength)

        {

            if (pattern[patternIndex] == pattern[len])

            {

                len++;

                lpsArray[patternIndex] = len;

                patternIndex++;

            }

            else

            {

                if (len == 0)

                {

                    lpsArray[patternIndex] = 0;

                    patternIndex++;

                }

                else

                {

                    len = lpsArray[len - 1];

                }

            }

        }

    }

​

​

}

​

public class RabinKarp : ISearch

{

​

    readonly static int primeNumber = 101;

    readonly static int d = 256;

​

​

    public IEnumerable<int> Search(string text, string pattern)

    {

        List<int> resultIndex = new List<int>();

​

        int patternLength = pattern.Length;

        int textLength = text.Length;

        int i, j;

​

        int patternHash = 0; // hash value for pattern  

        int textHash = 0; // hash value for txt  

        int h = 1;

​

        // The value of h would be "pow(d, M-1)%q"  

        for (i = 0; i < patternLength - 1; i++)

            h = (h * d) % primeNumber;

​

        // Calculate the hash value of pattern and first  

        // window of text  

        for (i = 0; i < patternLength; i++)

        {

            patternHash = (d * patternHash + pattern[i]) % primeNumber;

            textHash = (d * textHash + text[i]) % primeNumber;

        }

​

        // Slide the pattern over text one by one  

        for (i = 0; i <= textLength - patternLength; i++)

        {

​

            // Check the hash values of current window of text  

            // and pattern. If the hash values match then only  

            // check for characters on by one  

            if (patternHash == textHash)

            {

                /* Check for characters one by one */

                for (j = 0; j < patternLength; j++)

                {

                    if (text[i + j] != pattern[j])

                        break;

                }

​

                // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]  

                if (j == patternLength)

                    resultIndex.Add(i);

            }

​

            // Calculate hash value for next window of text: Remove  

            // leading digit, add trailing digit  

            if (i < textLength - patternLength)

            {

                textHash = (d * (textHash - text[i] * h) + text[i + patternLength]) % primeNumber;

​

                // We might get negative value of t, converting it  

                // to positive  

                if (textHash < 0)

                    textHash = (textHash + primeNumber);

            }

        }

​

        return resultIndex;

    }

​

}

​

​

public class BoyerMoore : ISearch

{

​

    public IEnumerable<int> Search(string text, string pattern)

    {

        List<int> retVal = new List<int>();

        int patternLength = pattern.Length;

        int textLength = text.Length;

​

        int[] badChar = new int[256];

​

        BadCharHeuristic(pattern, patternLength, ref badChar);

​

        int searchIndex = 0;

        while (searchIndex <= (textLength - patternLength))

        {

            int patternIndex = patternLength - 1;

​

            while (patternIndex >= 0 && pattern[patternIndex] == text[searchIndex + patternIndex])

                --patternIndex;

​

            if (patternIndex < 0)

            {

                retVal.Add(searchIndex);

                searchIndex += (searchIndex + patternLength < textLength) ? patternLength - badChar[text[searchIndex + patternLength]] : 1;

            }

            else

            {

                searchIndex += Math.Max(1, patternIndex - badChar[text[searchIndex + patternIndex]]);

            }

        }

​

        return retVal.ToArray();

    }

​

    private static void BadCharHeuristic(string str, int size, ref int[] badChar)

    {

        int i;

​

        for (i = 0; i < 256; i++)

            badChar[i] = -1;

​

        for (i = 0; i < size; i++)

            badChar[(int)str[i]] = i;

    }

​

}

​

public class StringSearchTest

{

    [Fact]

    public void KMP_Test()

    {

        ISearch kmpSearch = new KnuthMorrisPratt(); 

        AssertStringSearch(kmpSearch);

​

    }

​

    [Fact]

    public void BoyerMoore_Test()

    {

        ISearch kmpSearch = new BoyerMoore();

        AssertStringSearch(kmpSearch);

​

    }

​

    [Fact]

    public void RabinKarp_Test()

    {

        ISearch kmpSearch = new RabinKarp();

        AssertStringSearch(kmpSearch);

​

    }

​

​

​

    private void AssertStringSearch(ISearch searchAlgorithm)

    {

        string sampleText = "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=";

​

​

        string pattern1 = "abx";

        var pattern1Result = searchAlgorithm.Search(sampleText, pattern1).ToList();

        Assert.NotNull(pattern1Result);

        Assert.True(pattern1Result.Count() == 2);

        Assert.Equal(4, pattern1Result[0]);

        Assert.Equal(19, pattern1Result[1]);

​

​

        string pattern2 = "zf3";

        var pattern2Result = searchAlgorithm.Search(sampleText, pattern2).ToList();

        Assert.NotNull(pattern2Result);

        Assert.True(pattern2Result.Count() == 3);

        Assert.Equal(0, pattern2Result[0]);

        Assert.Equal(15, pattern2Result[1]);

        Assert.Equal(31, pattern2Result[2]);

​

    }

}

​

​

​

​

​