4.
Design, develop, and run a program in any language to solve the string matching
problem using nave approach and the KMP algorithm and compare their
Performances
using
using
using
using
using
System;
System.Collections.Generic;
System.Linq;
System.Text;
LabPrograms;
namespace ConsoleApplication
{
class Program
{
static void Main(string[] args)
{
TestStringMatch();
}
}
private static void TestStringMatch()
{
KPMStringMatcher stm=new KPMStringMatcher();
String givingString, subString;
Console.WriteLine("Enter String");
givingString = Console.ReadLine();
Console.WriteLine("Enter Sub String");
subString = Console.ReadLine();
Stopwatch sw = Stopwatch.StartNew();
// String Matching Using KPM Approch
stm.search(givingString, subString);
Console.WriteLine("_______________________________________________________
_");
Console.WriteLine("String Matching Using KPM Approch");
sw.Stop();
if(stm.ShowMatches.Contains('^'))
Console.WriteLine("Sub String {0} Found in Giving String
{1}",subString,givingString);
else
Console.WriteLine("Sub String {0} Not Found in Giving String
{1}", subString, givingString);
// Report the results
Console.WriteLine("Time used (float): {0} ms",
sw.Elapsed.TotalMilliseconds);
Console.WriteLine("Time used (rounded): {0} ms",
sw.ElapsedMilliseconds);
Console.WriteLine("_______________________________________________________
_");
Console.WriteLine("\nString Matching Using Native Approch");
sw.Start();
// String Macthing using Native Approch
NativeStringMatching nativeMatch = new NativeStringMatching();
int found = nativeMatch.NativeMatch(givingString,subString);
if(found==1)
Console.WriteLine("Sub String {0} Found in Giving String {1}",
subString, givingString);
else
Console.WriteLine("Sub String {0} Not Found in Giving String
{1}", subString, givingString);
// Report the results
Console.WriteLine("Time used (float): {0} ms",
sw.Elapsed.TotalMilliseconds);
Console.WriteLine("Time used (rounded): {0} ms",
sw.ElapsedMilliseconds);
Console.ReadLine();
}
using
using
using
using
System;
System.Collections.Generic;
System.Linq;
System.Text;
namespace LabPrograms
{
public class NativeStringMatching
{
public int NativeMatch(string text, string pattern)
{
for (int i = 0; i <= text.Length - pattern.Length; i++)
{
int j = 0;
while (j < pattern.Length &&
pattern[j] == text[i + j])
j++;
if (j == pattern.Length)
return 1;
}
return 0;
}
}
public class KPMStringMatcher
{
/** searches the text tt for the pattern pp */
private char[] p, t;
// pattern, text
private int m, n;
// pattern length, text length
private String matches; // string of match positions
private char[] showmatches;// char array that shows matches
private int[] b;
// used by the KMP algorithm
public char[] ShowMatches
{
get
{
return showmatches;
}
}
public void search(String tt, String pp)
{
setText(tt);
setPattern(pp);
kmpSearch();
}
/** sets the text */
private void setText(String tt)
{
n = tt.Length;
t = tt.ToCharArray();
initmatches();
}
/** sets the pattern */
private void setPattern(String pp)
{
m = pp.Length;
p = pp.ToCharArray();
b = new int[m + 1];
kmpPreprocess();
}
/** initializes match positions and the array showmatches*/
private void initmatches()
{
matches = "";
showmatches = new char[n];
for (int i = 0; i < n; i++)
showmatches[i] = ' ';
}
/** preprocessing of the pattern*/
private void kmpPreprocess()
{
int i = 0, j = -1;
b[i] = j;
while (i < m)
{
while (j >= 0 && p[i] != p[j])
j = b[j];
i++;
j++;
b[i] = j;
}
}
/** searches the text for all occurences of the pattern */
private void kmpSearch()
{
int i = 0, j = 0;
while (i < n)
{
while (j >= 0 && t[i] != p[j])
j = b[j];
i++;
j++;
if (j == m) // a match is found
{
report(i - m);
j = b[j];
}
}
}
/** reports a match*/
private void report(int i)
{
matches += i + " ";
showmatches[i] = '^';
}
/** returns the match positions after the search*/
public String getMatches()
{
return matches;
}
}
}
Output:
CASE 1:
Enter String
roshan
Enter Sub String
an
________________________________________________________
String Matching Using KPM Approch
Sub String an Found in Giving String roshan
Time used (float): 2.7536 ms
Time used (rounded): 2 ms
________________________________________________________
String Matching Using Native Approch
Sub String an Found in Giving String roshan
Time used (float): 3.6147 ms
Time used (rounded): 3 ms
CASE 2:
Enter String
roshan
Enter Sub String
rr
________________________________________________________
String Matching Using KPM Approch
Sub String rr Not Found in Giving String roshan
Time used (float): 1.4238 ms
Time used (rounded): 1 ms
________________________________________________________
String Matching Using Native Approch
Sub String rr Not Found in Giving String roshan
Time used (float): 2.0109 ms
Time used (rounded): 2 ms
