Create a program in \"JAVA\" that searches user inputted substring within the te

Question

Create a program in "JAVA" that searches user inputted substring within the text.

Requirements:

Program should read the text from file (number of characters > 200).

User should be able to search different substrings in the same file (looping).

The search should be implemented using one of the following algorithms (do not use built-in search

functions!!!):

Knuth-Morris-Pratt algorithm.

If substring is found, then program should output its start position in the text. If substring is not found, then program should output appropriate message.

Explanation / Answer

/**
** Java Program to implement Knuth Morris Pratt Algorithm
**/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.FileReader;

/** Class KnuthMorrisPratt **/
public class KnuthMorrisPratt
{
/** Failure array **/
private int[] failure;
/** Constructor **/
public KnuthMorrisPratt(String text, String pat)
{
/** pre construct failure array for a pattern **/
failure = new int[pat.length()];
fail(pat);
/** find match **/
int pos = posMatch(text, pat);
if (pos == -1)
System.out.println(" No match found");
else
System.out.println(" Match found at index "+ pos);
}
/** Failure function for a pattern **/
private void fail(String pat)
{
int n = pat.length();
failure[0] = -1;
for (int j = 1; j < n; j++)
{
int i = failure[j - 1];
while ((pat.charAt(j) != pat.charAt(i + 1)) && i >= 0)
i = failure[i];
if (pat.charAt(j) == pat.charAt(i + 1))

failure[j] = i + 1;
else
failure[j] = -1;
}
}
/** Function to find match for a pattern **/
private int posMatch(String text, String pat)
{
int i = 0, j = 0;
int lens = text.length();
int lenp = pat.length();
while (i < lens && j < lenp)
{
if (text.charAt(i) == pat.charAt(j))
{
i++;
j++;
}
else if (j == 0)
i++;
else
j = failure[j - 1] + 1;
}
return ((j == lenp) ? (i - lenp) : -1);
}
/** Main Function **/
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader (new FileReader("C:\testing.txt"));
System.out.println("Knuth Morris Pratt Test ");
System.out.println(" Enter Text ");
String text = br.readLine();
System.out.println(" Enter Pattern ");
String pattern = br.readLine();
KnuthMorrisPratt kmp = new KnuthMorrisPratt(text, pattern);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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