# O(N)

O(N)

A very good msdn article about computation of complexity

# 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);
}

}

///

/// 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)
{
}
}
}

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)
{
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

{

static void Main(string[] args)

{

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("-===================================================================================-");

}

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!

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’;

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

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

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

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

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

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

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

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

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

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

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

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

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() == ‘_’)) ;

}

/// <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]);

_machineState = _currentCommand.NextState;

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>

{

{

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

{

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

_tape[0] = ;

}

}

}

}

}

# Dec2Any

public static void Main()

{

try

{

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

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

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

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

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

}

catch(Exception
ex)

{

Console.WriteLine(ex.Message);

}

}

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: "
);

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

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

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

}

catch(Exception
ex)

{

Console.WriteLine(ex.Message);

}

}

/*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;

}

}