Question

Objectives
 To apply pattern matching algorithm concepts.
 To write the program to represent a Karp-Rabin method Problem
You are to implement the Karp-Rabin string search algorithm. Your program will prompt for the name of an input file and then read and process the data contained in this file. The file contains two sequences of characters. The first is the target sequence, T, the second is the search sequence S. Read both strings and find all occurrences of sequence S in sequence T using the Karp- Rabin algorithm. For each matched sequence, print the location of the first matched character in T.

For example, if the test data looked like this: ACGTACGTACCAGTA AC T
he output should be: 0, 4, 8
Notes: 1. The sequence T is no longer than 500 characters
2. The sequence S is no longer than 10 characters

has to be written in java

Answer 1

SOLUTION

CODE:

import java.util.Scanner;
import java.io.*;
public class StringMatching
{

public final static int SIZE = 500;

static void searchStr(String pat, String txt, int q)
{
int M = pat.length();
int N = txt.length();
int i, j;
int patt = 0;
int text = 0;
int h = 1;
  
  
for (i = 0; i < M-1; i++)
h = (h*SIZE)%q;
  
for (i = 0; i < M; i++)
{
patt = (SIZE*patt + pat.charAt(i))%q;
text = (SIZE*text + txt.charAt(i))%q;
}

for (i = 0; i <= N - M; i++)
{
  
if ( patt == text )
{
/* Check for characters one by one */
for (j = 0; j < M; j++)
{
if (txt.charAt(i+j) != pat.charAt(j))
break;
}
  
  
if (j == M)
System.out.println("Pattern found at index " + i);
}
  
if ( i < N-M )
{
text = (SIZE*(text - txt.charAt(i)*h) + txt.charAt(i+M))%q;
  
if (text < 0) //wrap for positive
text = (text + q);
}
}
}
  
public static void main(String[] args) throws FileNotFoundException
{
   Scanner sc=new Scanner(System.in);
   System.out.println("Enter name of File");
   String filename=sc.nextLine();
sc=new Scanner(new File(filename));
       String line=sc.nextLine();
String txt[] =line.split(" "); // dividing at space, characters before space are text and after space are pattern. text--->txt[0] AND pat------> txt[1]
int q = 101; // A prime number
searchStr(txt[1], txt[0], q);
}
}

CODE SCREENSHOT

OUTPUT

FILE: input.txt

ACGTACGTACCAGTA AC