Algorithm Help in Visual Studio using C#: I have the below code for a Knuth Morr
ID: 3916275 • Letter: A
Question
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();
This is code i received from online that can give another perception, but i wan to enter the code and not have the code already in the console.
// C# program for implementation of KMP pattern
// searching algorithm
using System;
class GFG {
void KMPSearch(string pat, string txt)
{
int M = pat.Length;
int N = txt.Length;
// create lps[] that will hold the longest
// prefix suffix values for pattern
int []lps = new int[M];
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[]
// array)
computeLPSArray(pat,M,lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
Console.Write("Found pattern "+
"at index " + (i-j));
j = lps[j-1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else
i = i+1;
}
}
}
void computeLPSArray(string pat, int M, int []lps)
{
// length of the previous longest prefix suffix
int len = 0;
int i = 1;
lps[0] = 0; // lps[0] is always 0
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
// This is tricky. Consider the example.
// AAACAAAA and i = 7. The idea is similar
// to search step.
if (len != 0)
{
len = lps[len-1];
// Also, note that we do not increment
// i here
}
else // if (len == 0)
{
lps[i] = len;
i++;
}
}
}
}
// Driver program to test above function
public static void Main()
{
string txt = "ABABDABACDABABCABAB";
string pat = "ABABCABAB";
new KMP_String_Matching().KMPSearch(pat,txt);
}
}
CAUsersbirDesktopWife's FolderKM PKMPin,DebugKMP.exe Enter the pattern you want to search: TATACCCATCCTTCCAATAATCACTAACTACTTCATATCCAATCCATAAAATAACTATTCCCTAAAATTACCCAAATACTCATTCATAACTTCAAATACCACTCTTCCATCCTAATAAAC CTCCACATCATTCATAAATCTATATAOCAATTTTTTAC CCTCCACTACCATAAATTCTTCATCCACATCTCAATACAACATACTATCCCTACTCCACAACTTCATTACCCTCTAACTTTTAATATACATAAACCCATCACAAAAAAAACATATTCACO CACAACCTCTAATCATTCATAACTTTTCTAATATAAAACATCTCCTTCACACATTTTACCTCCTTCCCCATTACAACATCCTTTAAACATCCTACTCCAATCAATCCTTACACCCCATTA TACATCAAATTACTAATTAATCTCTTATACATAATTACCCCTACCCTACCTCTATTCATCTTCTAACCCCATCATACTCCACTTATAATCTAACAACCTCACAATACATTCAACCTCAAG ATACAAAAAAACCACATTCCCCTAATCTCCATTCTTCTATACATAAACCCCTATAAACCTATATCTAATTTATTCCCACAACCACCTACTTCTTTTTCTTCAATATACTAAACCTTTATA AAAAACCCCAAATAACTTCATTTCATCCCAAAAATCACATCACTCATCTTCAATTTTTACCCCCAAATCTCTATATCACACAATACACCCATCTTCACTCCACATACCAACTTACTCTTA ATTAATCCCAACCAACTACCAATTACATTAACAACTTCCATAACCCTAACACTCACCACAAAACAATTTTTTATTCACTATCACCTATCCCTCTAACATCTCCTTTTCAACCTCCTATCO ACCTCACCTAACACTTCTAACATTACCCTTATACTTATCTCCTCACCTATTTACCCTAACACAAATTAACAACCTACTTAATTAACTTACAAAAACCTCCTTAATTCATCACTACTACAT AAATCCCCCTTTCCCTATCTAAATTATAATTCTTTTTTTT Pattern found at:1 Pattern found at:2 Pattern found at:3 Pattern found at:4 Pattern found at:1 Pattern found at:2 Pattern found at:3 Pattern found at:4Explanation / Answer
#Please use this code.
The PrefixArray class takes a string parameter, the pattern, and is responsible for calculating the prefix function and returning an array that contains the transition indexes.
In calculating the prefix array, care has been taken to give maximum performance; hence, the general implementation has been tweaked in several places.
The code above shows computing the prefix function; the loop in the code iterates through the pattern and calculates the prefix function for each index. (Note: the iteration starts from 1 as we know that the transition at index 0 is 0.)
The temp array represents all the characters from the 0th index of the pattern to the index of the current loop. This character array is passed into the GetPrefixLength() function, which actually computes the prefix function.
Next, we have the code for the GetPrefixLength() function:
This function takes in the array we discussed as a parameter, and also the first character of the pattern (charToMatch).
The array is iterated and searched for a match with the first character of the pattern (the first character needs to be matched, the prefix starts with the first character). If the first character exist in the array, then we calculate the longest suffix that is a prefix of the pattern.
Obviously, the first match gives us the longest suffix that is a prefix of the pattern.
The code below depicts the function IsSufficExists():
Next, we will look into the code snippet that actually finds the occurrence of the pattern in a string using the transition array for the pattern.
The loop iterates through the string to search the pattern. If the current character matches the character in the pattern index (the character index that should be matched in the iteration), then there is a match, and we increment the index of the pattern and continue.
If there is a mismatch, then we get the transition index for the specific index, and we see if the character at the transition index + 1 matches with the character that is being matched (this is done so we don’t need to unnecessarily match the character again). If there is a match, then we move the pattern index with the transition index; if not, we move the pattern index with 0.
Next, we see if the pattern index is equal to the pattern length; if so, then we have a match. This code snippet is shown below:
Using the code
In order to use the code, all you got to do is build the files in the source provided, and use the static method GetAllOccurences(string pattern, string text) of the KMPUtil class like this:
This method will return an ArrayList of indexes where the pattern occurs in the text (zero based).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.