using System;using System.Collections.Generic;namespace Dijistra{    /// <summary>    /// An implemention of Boyer-Moore algorithm.    /// <para/>author : Ornithopter    /// </summary>    class BoyerMooreSearch : IAlgorithm    {        /// <summary>        ///         /// </summary>        /// <param name="source"></param>        /// <param name="pattern"></param>        /// <returns>An array of matched index</returns>        public int[] Search(string source, string pattern)        {            var matchIndexes = new List<int>();            // step increasment.            var delta = 0;            // prepare a map providing delta for each char in pattern string.            var deltaMap = CreateDeltaMap(pattern);            // for display.            var indent = pattern.Length;            DebugUtil.WriteLine(source);            // start searching.            for (int i = pattern.Length - 1; i < source.Length; i += delta)            {                // for display.                indent += delta;                DebugUtil.Write(String.Format("{0}({1})", pattern.PadLeft(indent, ‘.‘), delta));                // find next match and update delta.                if (FindNext(source, pattern, i, deltaMap, out delta))                {                    // add to result list if found.                    matchIndexes.Add(i - (pattern.Length - 1));                    DebugUtil.Write("√");                }                // new line.                DebugUtil.WriteLine();            }            return matchIndexes.ToArray();        }        /// <summary>        /// Find the next matched index and update delte at the same time.        /// </summary>        /// <param name="source"></param>        /// <param name="pattern"></param>        /// <param name="start"></param>        /// <param name="deltaMap"></param>        /// <param name="delta"></param>        /// <returns>true if found one, otherwise false.</returns>        private bool FindNext(string source, string pattern, int start, int[] deltaMap, out int delta)        {            int i = pattern.Length - 1,                index = 0;            // start comparing from the last char in pattern.            while (source[start - index] == pattern[i - index])            {                if (index != pattern.Length - 1)                {                    index++;                }                else                {                    // matchs to the end. So it‘s a search result.                    delta = pattern.Length;                    return true;                }            }            // found one dismatched char, get delta from map.            delta = deltaMap[source[start]];            if (delta == 0)            {                // this means the source[start] char is the last char in pattern                // and only appears once. So delta should be the length of pattern.                delta = pattern.Length;            }            return false;        }        int[] CreateDeltaMap(string pattern)        {            const int AlphabetSize = 128;            int patternLength = pattern.Length;            var deltaMap = new int[AlphabetSize];            // initialize the map.            for (int i = 0; i < AlphabetSize; i++)            {                deltaMap[i] = patternLength;            }            // start from 0, which means any duplicated char will only have            // the index nearest to the end.            for (int i = 0; i < patternLength; i++)            {                deltaMap[pattern[i]] = patternLength - i - 1;            }            return deltaMap;        }        public void ShowExample()        {            // source string and pattern string are in one string and splited by ‘,‘.            var examples = new[]             {                "a b,b",                "AAAABAA,BA",                "awataa,wat",                "here is a simple example,ample",                "here is a simple example,example",                "AAAABAAAABAAABAAA,AB",                "awaaaaaaaawrwatawt,awrwatawt",            };            foreach (var example in examples)            {                var source = example.Split(‘,‘)[0];                var pattern = example.Split(‘,‘)[1];                var result = Search(source, pattern);                DebugUtil.WriteLine("{0} <-> {1} : {2}", source, pattern, String.Join(",", result));            }                    }    }}