String matching algorithms

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace NaiveStringMatcher
{
class Program
{
static void Main(string[] args)
{
string str = @”BANAN BANBAN BANBANANA BANAN BANAN BANANAN BANANANANANANANANAN”;

string pattern = “NANAN”;

float numTries = 10000;

List shifts = null;

Stopwatch stopWatch = new Stopwatch();

stopWatch.Start();

for (int i = 0; i < numTries; i++ )
shifts = NaiveStringMatcher(str, pattern);

stopWatch.Stop();

Trace.WriteLine(String.Format("Naive string matcher {0}", stopWatch.ElapsedMilliseconds / numTries));

foreach (var item in shifts)
{
Trace.WriteLine(item);
}

stopWatch.Restart();

for (int i = 0; i < numTries; i++)
shifts = Knuth_Morris_Pratt(str, pattern);

stopWatch.Stop();
Trace.WriteLine(String.Format("Knuth_Morris_Pratt {0}", stopWatch.ElapsedMilliseconds / numTries));

foreach (var item in shifts)
{
Trace.WriteLine(item);
}

Console.ReadKey();
}

///

/// The naive algorithm has one phase: it does a search.
/// It does that search much less efficiently in the worst case than the KMP search phase.
///
/// The Naive String Matcher algorithm takes time O((n – m + 1)m, and this bound is tight in the worst case.
///

/// text
/// pattern
/// shifts
static List NaiveStringMatcher(string text, string pattern)
{
int textLength = text.Length;
int patternLength = pattern.Length;

List shifts = new List();

for (int s = 0; s <= textLength – patternLength; s++)
{
//if we meet a character which is equal to the first
//character of the pattern we should take a chance and
//try to compare with other characters of the pattern
if (text[s] == pattern[0])
{
int i = 1;
while (i < patternLength)
{
if (text[s + i] == pattern[i])
i++;
//in case we are unhappy we have to try again from the position of s
else break;
}
if (i == patternLength)
{
shifts.Add(s);
}
}
}

return shifts;
}

///

/// The KMP algorithm has two phases: first it builds a table, and then it does a search,
/// directed by the contents of the table.
/// KMP is only a win if you have enormous strings and you are doing lots of searches that allow you to re-use an
/// already-built table. You need to amortize away the huge cost of building the table by doing lots of searches
/// using that table.
///
/// Preprocessing time is Θ(m) and matching time is Θ(n).
/// m is the pattern length
/// n is the text length
///

/// text
/// pattern
/// shifts
static List Knuth_Morris_Pratt(string text, string pattern)
{

int patternLength = pattern.Length;
int textLength = text.Length;

List shifts = new List();

int[] pi = ComputePrefixFunction(pattern);

int matchedSymNum = 0;

//Start scanning the text from the first symbol
for (int i = 0; i 0 && pattern[matchedSymNum] != text[i])
matchedSymNum = pi[matchedSymNum – 1];

//Scanning for the first match or
//Checking whether the symbol of the pattern at the calculated position
//is equal to the symbol of the text at the iterator’s position
//and increasing the number of matching symbols
if (pattern[matchedSymNum] == text[i])
matchedSymNum++;

//When the number of the matches is equal to the pattern length
//it means that we get a shift
if (matchedSymNum == patternLength)
{
shifts.Add(i – patternLength + 1);
matchedSymNum = pi[matchedSymNum – 1];
}

}

return shifts;
}

///

/// Builds a table with values of lengths beetwen matches
///
/// For example:
/// ababaca
/// 0012301
///

///
///
static int[] ComputePrefixFunction(string pattern)
{
int j;

int[] pi = new int[pattern.Length];

///The first value of pi[] is zero by default
//so we start scanning from 1
for (int i = 1; i < pi.Length; i++)
{
j = 0;
//If we find a match we start scanning inside the loop
//increasing the counter of matches
while((i < pi.Length) && (pattern[i] == pattern[j]) )
{
j++;
pi[i++] = j;
}
}

return pi;
}
}
}

String reverse

    class Program

    {

        private const string string2Reverse = "Loremipsumdolorsitamet,consecteturadipiscingelitUtcondimentumbibendumarcuquiscommodoNullamturpisdolor,interdumaccumsanvestibulumet,elementumnecnibhNammattis,augueactristiquecongue,nuncelitadipiscingdui,uthendreritestmaurisetdiamUtpellentesqueauctorerosinposuereVestibulumvitaeeniminelitmolestietristiquepulvinareumiNullanonquamatellusaccumsanluctusUtvulputatetristiquepretiumLoremipsumdolorsitamet,consecteturadipiscingelitDuisvitaepulvinarvelitCrasvitaemattisdiamSedegettellusnibhSuspendissesempertortoratantevestibulumcursus";

        static void Main(string[] args)

        {

 

            Thread.Sleep(1000);

           

            Stopwatch sw = Stopwatch.StartNew();

 

            Trace.WriteLine(StrRev(string2Reverse));

            Trace.WriteLine("Array.Reverse: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            sw = Stopwatch.StartNew();

            Trace.WriteLine(StrRev1(string2Reverse));

            Trace.WriteLine("Linq: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            sw = Stopwatch.StartNew();

            Trace.WriteLine(StrRev2(string2Reverse));

            Trace.WriteLine("StringBuilder: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            sw = Stopwatch.StartNew();

            Trace.WriteLine(StrRev3(string2Reverse));

            Trace.WriteLine("Array: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            sw = Stopwatch.StartNew();

            Trace.WriteLine(StrRev4(string2Reverse));

            Trace.WriteLine("Unsafe array: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            sw = Stopwatch.StartNew();

            Trace.WriteLine(StrRev5(string2Reverse));

            Trace.WriteLine("Unsafe array2: " + sw.Elapsed);

            Trace.WriteLine("-===================================================================================-");

 

            Console.ReadKey();

        }

 

        public static string StrRev(string source)

        {

            char []result = source.ToCharArray();

            Array.Reverse(result);

            return new String(result);

        }

 

        public static string StrRev1(string source)

        {                       

            return new String(source.Reverse().ToArray());

        }

 

        public static string StrRev2(string source)

        {

            if (source.Length == 1) return source;

 

            StringBuilder sb = new StringBuilder(source.Length);

            int i = source.Length – 1;

 

            while(i != -1)

            {

                sb.Append(source[i–]);

            }

 

            return sb.ToString();

        }

 

        public static string StrRev3(string source)

        {

            if (source.Length == 1) return source;

 

            char[] resultArray = new char[source.Length];

            int i = 0;

            int j = source.Length – 1;

            char temp = ;

 

            while ( i < j )

            {

                temp = source[i];

                resultArray[i] = source[j];

                resultArray[j] = temp;

                i++;

                j–;

            }

 

            return new String(resultArray);

        }

 

        public static unsafe string StrRev4(string source)

        {

            if (source.Length == 1) return source;

           

            int i = 0;

            int j = source.Length – 1;

 

            fixed (char* sourceArray = source)

            {

                char temp = ;

 

                while ( i < j )

                {

                    temp = sourceArray[i];

                    sourceArray[i] = sourceArray[j];

                    sourceArray[j] = temp;

                    i++;

                    j–;

                }

 

                return new String(sourceArray);

            }           

        }

 

        public static unsafe string StrRev5(string source)

        {

            if (source.Length == 1) return source;           

 

            fixed (char* sourceArray = source)

            {

                char temp = ;

 

                char* i = sourceArray;

                char* j = &sourceArray[source.Length – 1];

 

                while (i < j)

                {

                    temp = *i;

                    *i = *j;

                    *j = temp;

 

                    i++;

                    j–;

                }                

            }

 

            return source;           

        }

 

    }

 

susrucmulubitsevetnatarotrotrepmesessidnepsuShbinsullettegedeSmaidsittameativsarCtilevranivlupeativsiuDtilegnicsipidarutetcesnoc,tematisrolodmuspimeroLmuiterpeuqitsirtetatupluvtUsutculnasmuccasulletamauqnonalluNimueranivlupeuqitsirteitselomtilenimineeativmulubitseVereusopnisorerotcuaeuqsetnelleptUmaidtesiruamtsetirerdnehtu,iudgnicsipidatilecnun,eugnoceuqitsirtcaeugua,sittammaNhbincenmutnemele,temulubitsevnasmuccamudretni,rolodsiprutmalluNodommocsiuqucramudnebibmutnemidnoctUtilegnicsipidarutetcesnoc,tematisrolodmuspimeroL

Array.Reverse: 00:00:00.0176674

-===================================================================================-

susrucmulubitsevetnatarotrotrepmesessidnepsuShbinsullettegedeSmaidsittameativsarCtilevranivlupeativsiuDtilegnicsipidarutetcesnoc,tematisrolodmuspimeroLmuiterpeuqitsirtetatupluvtUsutculnasmuccasulletamauqnonalluNimueranivlupeuqitsirteitselomtilenimineeativmulubitseVereusopnisorerotcuaeuqsetnelleptUmaidtesiruamtsetirerdnehtu,iudgnicsipidatilecnun,eugnoceuqitsirtcaeugua,sittammaNhbincenmutnemele,temulubitsevnasmuccamudretni,rolodsiprutmalluNodommocsiuqucramudnebibmutnemidnoctUtilegnicsipidarutetcesnoc,tematisrolodmuspimeroL

Linq: 00:00:00.0064376

-===================================================================================-

susrucmulubitsevetnatarotrotrepmesessidnepsuShbinsullettegedeSmaidsittameativsarCtilevranivlupeativsiuDtilegnicsipidarutetcesnoc,tematisrolodmuspimeroLmuiterpeuqitsirtetatupluvtUsutculnasmuccasulletamauqnonalluNimueranivlupeuqitsirteitselomtilenimineeativmulubitseVereusopnisorerotcuaeuqsetnelleptUmaidtesiruamtsetirerdnehtu,iudgnicsipidatilecnun,eugnoceuqitsirtcaeugua,sittammaNhbincenmutnemele,temulubitsevnasmuccamudretni,rolodsiprutmalluNodommocsiuqucramudnebibmutnemidnoctUtilegnicsipidarutetcesnoc,tematisrolodmuspimeroL

StringBuilder: 00:00:00.0017977

-===================================================================================-

susrucmulubitsevetnatarotrotrepmesessidnepsuShbinsullettegedeSmaidsittameativsarCtilevranivlupeativsiuDtilegnicsipidarutetcesnoc,tematisrolodmuspimeroLmuiterpeuqitsirtetatupluvtUsutculnasmuccasulletamauqnonalluNimueranivlupeuqitsirteitselomtilenimineeativmulubitseVereusopnisorerotcuaeuqsetnelleptUmaidtesiruamtsetirerdnehtu,iudgnicsipidatilecnun,eugnoceuqitsirtcaeugua,sittammaNhbincenmutnemele,temulubitsevnasmuccamudretni,rolodsiprutmalluNodommocsiuqucramudnebibmutnemidnoctUtilegnicsipidarutetcesnoc,tematisrolodmuspimeroL

Array: 00:00:00.0017920

 

-===================================================================================-

susrucmulubitsevetnatarotrotrepmesessidnepsuShbinsullettegedeSmaidsittameativsarCtilevranivlupeativsiuDtilegnicsipidarutetcesnoc,tematisrolodmuspimeroLmuiterpeuqitsirtetatupluvtUsutculnasmuccasulletamauqnonalluNimueranivlupeuqitsirteitselomtilenimineeativmulubitseVereusopnisorerotcuaeuqsetnelleptUmaidtesiruamtsetirerdnehtu,iudgnicsipidatilecnun,eugnoceuqitsirtcaeugua,sittammaNhbincenmutnemele,temulubitsevnasmuccamudretni,rolodsiprutmalluNodommocsiuqucramudnebibmutnemidnoctUtilegnicsipidarutetcesnoc,tematisrolodmuspimeroL

Unsafe array: 00:00:00.0018522

-===================================================================================-

 

The StrRev4 method changes const string! Wow!

 

Loremipsumdolorsitamet,consecteturadipiscingelitUtcondimentumbibendumarcuquiscommodoNullamturpisdolor,interdumaccumsanvestibulumet,elementumnecnibhNammattis,augueactristiquecongue,nuncelitadipiscingdui,uthendreritestmaurisetdiamUtpellentesqueauctorerosinposuereVestibulumvitaeeniminelitmolestietristiquepulvinareumiNullanonquamatellusaccumsanluctusUtvulputatetristiquepretiumLoremipsumdolorsitamet,consecteturadipiscingelitDuisvitaepulvinarvelitCrasvitaemattisdiamSedegettellusnibhSuspendissesempertortoratantevestibulumcursus

Unsafe array2: 00:00:00.0017094

-===================================================================================-

 

As we can see the Array reverse method is the safe and fast enough way to reverse string.

 

Turing machine (A-B)

//A – B Turing program

_tape =

new char[] { ‘|’, ‘|’, ‘|’, ‘|’,‘|’,‘-‘, ‘|’,‘|’ };

_machineState =

‘A’;

_commands.Add(

new Command(‘A’, ‘|’, ‘|’, Direction.Right, ‘A’));

_commands.Add(

new Command(‘A’, ‘-‘, ‘-‘, Direction.Left, ‘B’));

_commands.Add(

new Command(‘B’, ‘|’, , Direction.Right, ‘C’));

_commands.Add(

new Command(‘B’, , , Direction.Left, ‘B’));

_commands.Add(

new Command(‘C’, , , Direction.Right, ‘C’));

_commands.Add(

new Command(‘C’, ‘-‘, ‘-‘, Direction.Right, ‘D’));

_commands.Add(

new Command(‘D’, ‘|’, ‘|’, Direction.Right, ‘D’));

_commands.Add(

new Command(‘D’, , , Direction.Left, ‘E’));

_commands.Add(

new Command(‘E’, , , Direction.Left, ‘E’));

_commands.Add(

new Command(‘E’, ‘|’, , Direction.Left, ‘F’));

_commands.Add(

new Command(‘F’, ‘|’, ‘|’, Direction.Left, ‘G’));

_commands.Add(

new Command(‘F’, ‘-‘, ‘-‘, Direction.Left, ‘_’));

_commands.Add(

new Command(‘G’, ‘-‘, ‘-‘, Direction.Left, ‘B’));

Turing machine

http://en.wikipedia.org/wiki/Turing_machine

http://www.gotdotnet.ru/blogs/sos/5309/

http://www.gotdotnet.ru/blogs/vanka/5744/

 

http://lib.custis.ru/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0:%D0%A0%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8,_%D1%81_%D0%BE%D0%B4%D0%B8%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2%D1%8B%D0%BC_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%BE%D0%BC_0_%D0%B8_1

 

http://lib.custis.ru/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0:%D0%A0%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8

 

http://en.wikipedia.org/wiki/Turing_machine_examples

 

namespace TuringMachine

{

    /// <summary>

    /// Represents a direction of the Turings machine head

    /// </summary>

    public enum Direction

    {

        Left = -1,

        Right = 1,

        Hold = 0

    }

   

    /// <summary>

    /// Defines a specific command that you intend to execute against a data source

    /// </summary>

    public class Command

    {

        private char? _state = null;

        private char? _scannedData = null;

        private char? _putData = null;

        private Direction? _direction = null;

        private char? _nextState = null;       

 

        private Command(){}

 

        /// <summary>

        ///

        /// </summary>

        /// <param name="state">Current state</param>

        /// <param name="scannedData">Scanned symbol</param>

        /// <param name="putData">New symbol</param>

        /// <param name="direction">Direction of the Turings machine head</param>

        /// <param name="nextState">Next state</param>

        public Command(char state, char scannedData, char putData, Direction direction, char nextState)

        {

            _state= state;

            _scannedData = scannedData;

            _putData = putData;

            _direction = direction;

            _nextState = nextState;

        }

 

        public char? State

        {

            get { return _state; }

        }

 

        public char? ScannedData

        {

            get { return _scannedData; }

        }

 

        public char? NextState

        {

            get { return _nextState; }

        }

 

        public Direction? Direction

        {

            get { return _direction; }

        }

 

        public char? Data

        {

            get { return _putData; }

        }

    }

 

    class Program

    {

        private static int _headPosition = 0;

        private static char[] _tape = null;

        private static char? _machineState = null;

        private static List<Command> _commands = new List<Command>();

        private static Command _currentCommand = null;

       

        static void Main(string[] args)

        {

            //3-state busy beaver program

            _machineState = ‘A’;

            _tape = new char[] { };

 

            _commands.Add(new Command(‘A’, , ‘1’, Direction.Right, ‘B’));

            _commands.Add(new Command(‘A’, ‘1’, ‘1’, Direction.Left, ‘C’));

            _commands.Add(new Command(‘B’, , ‘1’, Direction.Left, ‘A’));

            _commands.Add(new Command(‘B’, ‘1’, ‘1’, Direction.Right, ‘B’));

            _commands.Add(new Command(‘C’, , ‘1’, Direction.Left, ‘B’));

            _commands.Add(new Command(‘C’, ‘1’, ‘1’, Direction.Hold, ‘_’));

 

            while (!(Run() == ‘_’)) ;

 

 

            Console.ReadKey();

        }

 

        /// <summary>

        /// The Turing machine reads a symbol from its tape and proccess a command

        /// </summary>

        /// <returns>Next state of the Turing Machine</returns>

        public static char? Run()

        {

 

            Trace.WriteLine(" -=====================================================- ");

            try

            {

                _currentCommand = _commands.Single(o => ((o.State == _machineState) && (o.ScannedData == _tape[_headPosition])));

            }

            catch(Exception ex)

            {

                //If there is no such command or there are more the one command it generates an exception 

                Trace.WriteLine("Ambigous command");

                return ‘_’;

            }

 

           

            Trace.WriteLine("Current machine state: " + _machineState);

            Trace.WriteLine("Data on the tape: " + _tape[_headPosition]);

           

            _tape[_headPosition] = (char)_currentCommand.Data;

            _machineState = _currentCommand.NextState;

            MoveHead(_currentCommand.Direction);           

 

            Trace.WriteLine("New data on the tape: " + _currentCommand.Data);

            Trace.WriteLine("New state: " + _currentCommand.NextState);

            Trace.WriteLine(" Direction: " + _currentCommand.Direction);

 

            return _machineState;

        }

 

        /// <summary>

        /// Moves the Turing machine head and if it is neccessary extends the tape

        /// </summary>

        /// <param name="direction">A direction of the Turings machine head</param>

        public static void MoveHead(Direction? direction)

        {

            _headPosition += (int)direction;

            if (_headPosition == _tape.Length || _headPosition == -1)

            {

                Array.Resize(ref _tape, _tape.Length + 1);

                if (_headPosition == -1)

                {

                    Array.ConstrainedCopy(_tape, 0, _tape, 1, _tape.Length – 1);

                    _tape[0] = ;

                    _headPosition = 0;

                }

            }

 

        }

    }

}

Dec2Any

                               public static void Main()

                               {

                                               try

                                               {

                                                               Console.Write("Enter
the number base: "
);

                                                               string baseData = Console.ReadLine();

                                                               int numberBase = int.Parse(baseData,
NumberStyles.Integer);

                                                               Console.Write("Enter
the number: "
);

                                                               string data = Console.ReadLine();

                                                               int number = int.Parse(data,
NumberStyles.Integer);

                                                               Console.WriteLine(GetDec2Any(numberBase, number));

                                               }

                                               catch(Exception
ex)

                                               {

                                                               Console.WriteLine(ex.Message);

                                               }

                                               Console.ReadKey();

                               }

                              

                              

                               public static string GetDec2Any(int
numberBase, int number)

                               {

                                               const string ABC = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";                                                                                       

                                               StringBuilder remainder = new
StringBuilder();

 

                                               while(numberBase <=  number)

                                               {

                                                               remainder.Insert(0,
ABC[number % numberBase]);

                                                               number
=  number / numberBase;                                                                                                                                                             

                                               }

 

                                               remainder.Insert(0,
ABC[number % numberBase]);

                                               return remainder.ToString();

                               }

Any2Dec

                class
Any2Dec

                {

                               public static void Main()

                               {

                                               try

                                               {

                                                               Console.Write("Enter
the number base: "
);

                                                               string baseData = Console.ReadLine();

                                                               int numberBase = int.Parse(baseData,
NumberStyles.Integer);

                                                               Console.Write("Enter
the number: "
);

                                                               string data = Console.ReadLine().ToUpperInvariant();

                                                               Console.WriteLine(GetAny2Dec(numberBase, data));

                                               }

                                               catch(Exception
ex)

                                               {

                                                               Console.WriteLine(ex.Message);

                                               }

                                               Console.ReadKey();

                               }

                              

                               /*Xp=An*P^(n-1) + An-1*P^(n-2)+An-2*P^(n-3)+…+A2P^1 +
A1P^0*/
              

                               public static long GetAny2Dec(int
numberBase, string data)

                               {

                                               const string ABC = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";                                                                                  

                                               long result = 0;

                                               for (int i =0; i <
data.Length; i++)

                                               {

                                                               result
+=  ABC.IndexOf(data[i]) * ((long)Math.Pow(numberBase
, data.Length – i – 1));                             

                                               }

                                               return result;

                               }

                }