(UVA) Longest Match - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1041

The solution below used the concept of Longest Common Subsequence (LCS), related to Dynamic Programming, to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public String[] s1;
    public String[] s2;
    public int[][] memo;
  
    public int rec(int indexS1, int indexS2) {
        if (indexS1 == s1.length || indexS2 == s2.length) {
            return 0;
        }
      
        if (memo[indexS1][indexS2] != -1) {
            return memo[indexS1][indexS2];
        }
      
        int jumpLeft = rec(indexS1+1, indexS2);
        int jumpRight = rec(indexS1, indexS2+1);
        int equal = (s1[indexS1].equals(s2[indexS2])) ? rec(indexS1+1, indexS2+1) + 1 : rec(indexS1+1, indexS2+1) + 0;
      
        memo[indexS1][indexS2] = Math.max(jumpLeft, Math.max(jumpRight, equal));
        return memo[indexS1][indexS2];
    }
  
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numCase = 0;
        String line = br.readLine();
        while (line != null) {
            boolean blank = false;
            if (line.equals("")) {
                blank = true;
            }
            s1 = line.split("[\\W]"); // we split the string by any character that it is not in a-z, A-Z, or 0-9
          
            line = br.readLine();
            if (line.equals("")) {
                blank = true;
            }
            s2 = line.split("[\\W]"); // we split the string by any character that it is not in a-z, A-Z, or 0-9
          
            memo = new int[s1.length][s2.length];
            for (int i = 0; i < s1.length; i++) {
                for (int j = 0; j < s2.length; j++) {
                    memo[i][j] = -1;
                }
            }
          
            if (blank) {
                String format = String.format("%2d. Blank!\n", ++numCase);
                bw.write(format);
            }
            else {
                String format = String.format("%2d. Length of longest match: %d\n", ++numCase, rec(0, 0));
                bw.write(format);
            }
          
            line = br.readLine();
        }
                                             
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}