Knuth Morris Pratt Algorithm Help in Visual Studio using C#: I have the below co

Question

Knuth Morris Pratt Algorithm Help in Visual Studio using C#:

I have the below code for a Knuth Morris Pratt Algorithm. I am unable to get the right results that gets printed to the console. Im having a hard time figuring out what is wrong with the code. I have pasted my results, my source code and how KMP works.

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMP
{
public class Program
{
string s;
string pattern;
int[] f = new int[100];
  

public Program(string name)
{

}

public void InputPattern()
{
Console.WriteLine("Enter the pattern you want to search: ");
pattern = (Console.ReadLine()).ToUpper(); //read user input

}

public void RandomGenerator()
{
Random geneSequence = new Random(); // The random number sequence

for (int i = 0; i < 1000; i++)
{
int x = geneSequence.Next(1, 4);

switch (x)
{
case 1:
s = s + 'C';
break;

case 2:
s = s + 'T';
break;

case 3:
s = s + 'A';
break;

case 4:
s = s + 'G';
break;
}

}

Console.WriteLine(s); //display results of string
}

public void preKMP()
{
int m = pattern.Length;
int k;
f[0] = -1;
for (int i = 1; i < m; i++)
{
k = f[i - 1];
while (k >= 0)
{
if (pattern[k] == pattern[i - 1])
break;
else
k = f[k];
}
f[i] = k + 1;

Console.WriteLine("Pattern found at:{0}", i);

Console.WriteLine(pattern);
}

}

public int Search() // s is string sequence, pattern is what is inputted from user
{

//kmp algorithm is executed here

int m = pattern.Length;
int n = s.Length;
int[] f = new int[m];

preKMP();
int i = 0;
int k = 0;

while (i < n)
{
if (k == -1)
{
++i;
k = 0;
}
else if (s[i] == pattern[k])
{
i++;
k++;
{

return 1;
}

}
else
k = f[k];
  
}

return 0;

  
}

public void DisplayTime()
{
var watch = System.Diagnostics.Stopwatch.StartNew();
// the code that you want to measure comes here
watch.Stop();
var elapsedMs = watch.ElapsedMilliseconds;

Console.WriteLine("Time processed: {0}ms", watch.ElapsedMilliseconds);
}

}

}

ProgramTest.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMP
{
public class ProgramTest
{
public static void Main(string[] args)
{
Program myProgram = new Program("Thank you for running the " +
"Knuth Morris Pratt Algorithm");

myProgram.InputPattern(); //read in the inputted pattern from user

myProgram.RandomGenerator(); //run the random generator program

myProgram.preKMP();
myProgram.Search();

myProgram.DisplayTime();

Console.Read();
}
}
}

Explanation / Answer

// I have tweaked your code a bit
// Kept Main method in Program.cs
// and other methods in a class name KMP
// Find the code in bold

// Program.cs
using System;

namespace ConsoleApp
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Knuth Morris Pratt Algorithm");
Console.WriteLine();

KMP kmp = new KMP();

string text = kmp.RandomGenerator();
Console.WriteLine(text);

// Get user input pattern
string pattern = kmp.GetInputPattern();

var result = kmp.KMPSearch(text, pattern);

Console.Write("Pattern found at : ");
for (int index=0; index<result.Count; index++)
{
Console.Write($" {result[index]} ");
}
Console.WriteLine();

kmp.DisplayTime();
Console.ReadLine();
}
}
}

// KMP.cs
using System;
using System.Collections.Generic;

namespace ConsoleApp
{
public class KMP
{
DateTime startTime = DateTime.Now;
DateTime endTime = DateTime.Now;

public string GetInputPattern()
{
Console.WriteLine();
Console.Write("Enter the pattern you want to search: ");
return (Console.ReadLine()).ToUpper(); //read user input
}
public string RandomGenerator()
{
string s = string.Empty;
Random geneSequence = new Random(); // The random number sequence

for (int i = 0; i < 1000; i++)
{
int x = geneSequence.Next(1, 4);
switch (x)
{
case 1:
s = s + 'C';
break;

case 2:
s = s + 'T';
break;

case 3:
s = s + 'A';
break;

case 4:
s = s + 'G';
break;
}

}
return s;
}

public void DisplayTime()
{
TimeSpan span = endTime - startTime;

Console.WriteLine("Time processed: {0}ms", span.TotalMilliseconds);
}

public List<int> KMPSearch(string text, string pattern)
{
startTime = DateTime.Now;

int N = text.Length;
int M = pattern.Length;

int[] lpsArray = new int[M];
List<int> matchedIndex = new List<int>();

if (N < M) return matchedIndex;
if (N == M && text == pattern) return matchedIndex;
if (M == 0) return matchedIndex;

LongestPrefixSuffix(pattern, ref lpsArray);

int i = 0, j = 0;
while (i < N)
{
if (text[i] == pattern[j])
{
i++;
j++;
}

// match found at i-j
if (j == M)
{
matchedIndex.Add(i - j);
//Console.WriteLine((i - j).ToString());
j = lpsArray[j - 1];
}
else if (i < N && text[i] != pattern[j])
{
if (j != 0)
{
j = lpsArray[j - 1];
}
else
{
i++;
}
}
}

endTime = DateTime.Now;
return matchedIndex;
}
public void LongestPrefixSuffix(string pattern, ref int[] lpsArray)
{
int M = pattern.Length;
int len = 0;
lpsArray[0] = 0;
int i = 1;

while (i < M)
{
if (pattern[i] == pattern[len])
{
len++;
lpsArray[i] = len;
i++;
}
else
{
if (len == 0)
{
lpsArray[i] = 0;
i++;
}
else
{
len = lpsArray[len - 1];
}
}
}
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.