HackerRank Stryker world code sprint - Java8 solution - use RabinKarp class, and also DP - dynamic programming - study code

TheHiddenMessage_java8.java

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();
    }

    
}