Please use java to write the code. The data of file is below: This exercise is t
ID: 3742067 • Letter: P
Question
Please use java to write the code. The data of file is below:
This exercise is to be done before or during your week 7 laboratory class. When you complete the exercise show your work to your lab tutor to have your work marked. The marking is based mainly on correct implementation and code readability. You should implement your code in one file (e.g ex6.cpp, ex6.c, ex6.java). Make sure your program has a header comment block containing the name of the exercise, your name and your student login (e.g. jfk01). You may implement your solution in C, C++, Java or Pythorn For this exercise, you are to implement the Karp-Rabin string search algorithm. As usual, your program will prompt for the name of an input file and the 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 The output should be 0,4, 8 Notes: 1. 2. 3. The sequence T is no longer than 5000 characters The sequence S is no longer than 10 characters The alphabet used in both sequences consists of the letters, A, C, G and T; the DNA base sequences Choose an appropriate modulus, m, for the hash function. Try to make your hash computation as efficient as possible. 4. 5. When you are finished, test your program using the provided text file named "Ex6.txt" and show your code and the output to your lab tutor to receive your mark.Explanation / Answer
import java.io.*;
import java.util.*;
// Defines class RabinKarpSearch
public class RabinKarpSearch
{
// charLen is the number of characters in the input alphabet
public final static int charLen = 256;
// To store original and pattern string
static String original = null;
static String pattern = null;
/*
* Method to search a string within another string using Rabin Karp Algorithm
* Parameter: String pattern and string to search and a prime number
*/
static void search(int primeNo)
{
// Stores the length of the pattern string
int patLen = pattern.length();
// Stores the length of the original string
int oriLen = original.length();
// Loops variables
int r, c;
// Hash value for pattern
int patHash = 0;
// Hash value for original
int oriHahs = 0;
int h = 1;
// Loops till length of the pattern
for (r = 0; r < patLen - 1; r++)
h = (h * charLen) % primeNo;
// Calculate the hash value of pattern and first window of text
for (r = 0; r < patLen; r++)
{
patHash = (charLen * patHash + pattern.charAt(r)) % primeNo;
oriHahs = (charLen * oriHahs + original.charAt(r)) % primeNo;
}// End of for loop
// Slide the pattern over text one by one
for (r = 0; r <= oriLen - patLen; r++)
{
// Check the hash values of current window of text
// and pattern. If the hash values match then only
// check for characters on by one
if (patHash == oriHahs)
{
/* Check for characters one by one */
for (c = 0; c < patLen; c++)
{
if (original.charAt(r + c) != pattern.charAt(c))
break;
}// End of inner for loop
// if p == t and pattern[0...M-1] = original[i, i+1, ...i+M-1]
if (c == patLen)
System.out.println("Pattern found at index " + r);
}// End of if condition
// Calculate hash value for next window of text:
// Remove leading digit, add trailing digit
if ( r < oriLen - patLen)
{
oriHahs = (charLen * (oriHahs - original.charAt(r) * h) + original.charAt(r + patLen)) % primeNo;
// We might get negative value of t, converting it to positive
if (oriHahs < 0)
oriHahs = (oriHahs + primeNo);
}// End of if condition
}// End of outer for loop
}// End of method
// method to read file contents
static void readFile(String fileName)
{
// Scanner class object declared
Scanner sc;
// Try block begins
try
{
// Opens the file for reading
sc = new Scanner(new File(fileName));
// Reads till end of the file
// Stores the data in original string
original = sc.nextLine();
// Close the scanner
sc.close();
}// End of try block
// Catch block to handle file not found exception
catch(FileNotFoundException foe)
{
System.out.print("Unable to read file " + fileName);
}// End of catch block
// Creates a scanner object to accept data from console
sc = new Scanner(System.in);
// Accepts the pattern
System.out.print(" String : " + original);
System.out.print(" Enter the pattern to search: ");
pattern = sc.next();
// Close the Scanner
sc.close();
}// End of method
// main function definition
public static void main(String[] args)
{
// A prime number
int prime = 101;
// Calls the method to read file contents
readFile("Search.txt");
// Calls the method to search
search(prime);
}// End of main function
}// End of class
Sample Output:
String : ATTGGTAAATACGGCTGTACGGTGCCGACTAAGCGGAATAGCCTACCACGTTACGGTATCTTCTTGCAAGTGTATTCTCGCACCTTAATTGTATCGGGAAGTAGGTTATGATGATAGAGACCCCCCCGGCACAAAACTTTCGGTAAGTGGAGCGCCCGACTGGCCGCCGGGATCAGAACGAACGATGCCCAGGGGCCGGCGGGCGATGAGCGACTTCGACGACCCAGGCTACGAATTCCCTGCCGACCCATTCTTGATGAAAAGCCCTGCTTCGGGACTGTCTGAAAATCTGTTTTTAGGGCACTTTGTCTCTTTCAAGGCAGTCCCTGGCGTGCTATCCGCATGGACATATCGCCATGACGACGATTGACCAGAGCAGCCTCAAAGTGGCAAATTCCTAACAGGCACCTACTTAGATGCGACGAGTAAAGCGCCGGGAAAGGTAACATGAACGGTTGAAAAATACAACGAGATACCGGGAGGGAAACTAGCAGATGCTCGGACATAGCACTCTGGGTCGCCGGAGGTGCCAAGTTAAAGCGCAACCAAGACTGGATCTGCCATCTCCTAAAGGGGAGCTGCTACCTACACATACTGTTCTCGTTGGATCGACCTTGCGTATATCCTGGGATCCACTACTTTGAATCACAGGAGCTACCCCTCGTATGGCTGATTGGCGGCCACCGTTTCCCGACAGACTGTCTGCTACGTTAGGTTACTAAATGACCGACAGCTAGACCGGGAGGTCAATTTTGGATTTCTATAGTCATCAACCACTGCGGTTGGCATCCCATAACCCGGCGCACTATGCTGCACACGAGGACTGTCAATAGCTTCGGCCACGCAGGCTAACGGCTCGAGGCATGGGTAAGGTTGCTCGAGCCGGCGCCACACCAGCTCTTACTCCATATCAGCCGGCGCGACCACAGGGAGGGCCAAAAGCGTGCGAAACATGCATCTACTCTCTCTACTCGCCGTCAAGCCAATTGTAGGACGGCAAATCGACATCTATGATCTTTGATCG
Enter the pattern to search: AC
Pattern found at index 10
Pattern found at index 18
Pattern found at index 27
Pattern found at index 44
Pattern found at index 47
Pattern found at index 52
Pattern found at index 81
Pattern found at index 119
Pattern found at index 130
Pattern found at index 135
Pattern found at index 158
Pattern found at index 177
Pattern found at index 181
Pattern found at index 212
Pattern found at index 218
Pattern found at index 221
Pattern found at index 230
Pattern found at index 245
Pattern found at index 276
Pattern found at index 302
Pattern found at index 346
Pattern found at index 359
Pattern found at index 362
Pattern found at index 369
Pattern found at index 400
Pattern found at index 406
Pattern found at index 410
Pattern found at index 421
Pattern found at index 445
Pattern found at index 451
Pattern found at index 464
Pattern found at index 467
Pattern found at index 474
Pattern found at index 486
Pattern found at index 502
Pattern found at index 509
Pattern found at index 544
Pattern found at index 550
Pattern found at index 583
Pattern found at index 587
Pattern found at index 589
Pattern found at index 593
Pattern found at index 611
Pattern found at index 634
Pattern found at index 637
Pattern found at index 647
Pattern found at index 656
Pattern found at index 682
Pattern found at index 693
Pattern found at index 697
Pattern found at index 707
Pattern found at index 717
Pattern found at index 725
Pattern found at index 729
Pattern found at index 737
Pattern found at index 772
Pattern found at index 775
Pattern found at index 795
Pattern found at index 804
Pattern found at index 814
Pattern found at index 816
Pattern found at index 822
Pattern found at index 841
Pattern found at index 851
Pattern found at index 890
Pattern found at index 892
Pattern found at index 902
Pattern found at index 922
Pattern found at index 925
Pattern found at index 950
Pattern found at index 960
Pattern found at index 969
Pattern found at index 993
Pattern found at index 1004
Search.txt file contents
ATTGGTAAATACGGCTGTACGGTGCCGACTAAGCGGAATAGCCTACCACGTTACGGTATCTTCTTGCAAGTGTATTCTCGCACCTTAATTGTATCGGGAAGTAGGTTATGATGATAGAGACCCCCCCGGCACAAAACTTTCGGTAAGTGGAGCGCCCGACTGGCCGCCGGGATCAGAACGAACGATGCCCAGGGGCCGGCGGGCGATGAGCGACTTCGACGACCCAGGCTACGAATTCCCTGCCGACCCATTCTTGATGAAAAGCCCTGCTTCGGGACTGTCTGAAAATCTGTTTTTAGGGCACTTTGTCTCTTTCAAGGCAGTCCCTGGCGTGCTATCCGCATGGACATATCGCCATGACGACGATTGACCAGAGCAGCCTCAAAGTGGCAAATTCCTAACAGGCACCTACTTAGATGCGACGAGTAAAGCGCCGGGAAAGGTAACATGAACGGTTGAAAAATACAACGAGATACCGGGAGGGAAACTAGCAGATGCTCGGACATAGCACTCTGGGTCGCCGGAGGTGCCAAGTTAAAGCGCAACCAAGACTGGATCTGCCATCTCCTAAAGGGGAGCTGCTACCTACACATACTGTTCTCGTTGGATCGACCTTGCGTATATCCTGGGATCCACTACTTTGAATCACAGGAGCTACCCCTCGTATGGCTGATTGGCGGCCACCGTTTCCCGACAGACTGTCTGCTACGTTAGGTTACTAAATGACCGACAGCTAGACCGGGAGGTCAATTTTGGATTTCTATAGTCATCAACCACTGCGGTTGGCATCCCATAACCCGGCGCACTATGCTGCACACGAGGACTGTCAATAGCTTCGGCCACGCAGGCTAACGGCTCGAGGCATGGGTAAGGTTGCTCGAGCCGGCGCCACACCAGCTCTTACTCCATATCAGCCGGCGCGACCACAGGGAGGGCCAAAAGCGTGCGAAACATGCATCTACTCTCTCTACTCGCCGTCAAGCCAATTGTAGGACGGCAAATCGACATCTATGATCTTTGATCG
AGCTA