Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
HackerRank Stryker world code sprint - Java8 solution - use RabinKarp class, and also DP - dynamic programming - study code
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String text = scan.nextLine();
String[] pat = scan.nextLine().split(" ");
List<Integer> matchPos = new ArrayList<Integer>();
int start = 0;
for (String p : pat) {
RabinKarp rk = new RabinKarp(p);
int mp = rk.search(text, start);
if (mp >= text.length()) {
break;
}
matchPos.add(mp);
start = mp+1;
}
if (matchPos.size() == pat.length) {
System.out.println("YES");
} else {
System.out.println("NO");
}
boolean insertSpace = false;
for (int i=0;i<matchPos.size();i++) {
if (insertSpace) System.out.print(" ");
insertSpace = true;
System.out.print(pat[i] + " " + matchPos.get(i) + " " + (matchPos.get(i) + (pat[i].length()-1)) );
}
if (matchPos.size() == 0) System.out.print("0");
System.out.println();
if (matchPos.size() != pat.length) System.out.println(0);
else {
int pLen = 0;
for (String p:pat)pLen+=p.length();
int lc = lcs(text, pat);
System.out.println(text.length()-lc + pLen-lc + pat.length-1);
}
}
private static int lcs(String text, String[] pat) {
String pattern = "";
for (String p:pat) {
pattern += p;
}
int m = text.length();
int n = pattern.length();
int[][] dp = new int[m+1][n+1];
for (int i=1;i<=m;i++) {
for (int j=1;j<=n;j++) {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
if (text.charAt(i-1) == pattern.charAt(j-1)) {
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
}
}
}
return dp[m][n];
}
}
class RabinKarp {
private String pat; // the pattern // needed only for Las Vegas
private long patHash; // pattern hash value
private int m; // pattern length
private long q; // a large prime, small enough to avoid long overflow
private int R; // radix
private long RM; // R^(M-1) % Q
/**
* Preprocesses the pattern string.
*
* @param pattern the pattern string
* @param R the alphabet size
*/
public RabinKarp(char[] pattern, int R) {
throw new UnsupportedOperationException("Operation not supported yet");
}
/**
* Preprocesses the pattern string.
*
* @param pat the pattern string
*/
public RabinKarp(String pat) {
this.pat = pat; // save pattern (needed only for Las Vegas)
R = 256;
m = pat.length();
q = longRandomPrime();
// precompute R^(m-1) % q for use in removing leading digit
RM = 1;
for (int i = 1; i <= m-1; i++)
RM = (R * RM) % q;
patHash = hash(pat, m);
}
// Compute hash for key[0..m-1].
private long hash(String key, int m) {
long h = 0;
for (int j = 0; j < m; j++)
h = (R * h + key.charAt(j)) % q;
return h;
}
private long hash(String key, int start, int m) {
long h = 0;
for (int j = 0; j < m; j++)
h = (R * h + key.charAt(start+j)) % q;
return h;
}
// Las Vegas version: does pat[] match txt[i..i-m+1] ?
private boolean check(String txt, int i) {
for (int j = 0; j < m; j++)
if (pat.charAt(j) != txt.charAt(i + j))
return false;
return true;
}
/**
* Returns the index of the first occurrrence of the pattern string
* in the text string.
*
* @param txt the text string
* @return the index of the first occurrence of the pattern string
* in the text string; n if no such match
*/
public int search(String txt, int start) {
int n = txt.length();
if (n-start < m) return n;
long txtHash = hash(txt, start, m);
// check for match at offset 0
if ((patHash == txtHash) && check(txt, start))
return start;
// check for hash match; if hash match, check for exact match
for (int i = start+m; i < n; i++) {
// Remove leading digit, add trailing digit, check for match.
txtHash = (txtHash + q - RM*txt.charAt(i-m) % q) % q;
txtHash = (txtHash*R + txt.charAt(i)) % q;
// match
int offset = i - m + 1;
if ((patHash == txtHash) && check(txt, offset))
return offset;
}
// no match
return n;
}
// a random 31-bit prime
private static long longRandomPrime() {
BigInteger prime = BigInteger.probablePrime(31, new Random());
return prime.longValue();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.