A very good msdn article about computation of complexity
Category: Algorithms
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();
}
///
/// 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;
}
///
/// 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;
}
///
///
/// 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)
_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://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;
}
}