Competitive Programming: SPOJ – String Problem

Link to problem

Substring of some string A is defined as one or more (not necessary succeeding) elements of the string with maintaining the sequence.

There are given two strings, string VOKI and string TOKI. Write the program that will calculate the length of any shortest substring of string VOKI such as it is not substring of string TOKI.

Input

In first line of input file there is string VOKI and in second one is string TOKI. The only characters that will occur are lowercase characters of English alphabet (‘a’- ‘z’). String lengths will be less or equal to 1000.

Note: input data will be such so there will always be a solution.

Output

In the first line of file you should print the length of wanted substring.

Sample input
 
banana 
anbnaanbaan 
 
Sample output
 
5 
 
(eg. banna) 

Sample input
 
babab 
babba 
 
Sample output
 
3 
 
(eg. aab)

Solution below . . .

Steps for Solving Dynamic Programming Problems

Instead of VOKI and TOKI, let’s just call the strings S and T. NB: The problem defines substring to mean what is normally called a subsequence. A subsequence need not be consecutive, e.g., bcab is a subsequence of abcbdab.

1. Define subproblems

Let $D_{ij}$ be the length of the shortest substring of $S_{1...i}$ that is not a substring of $T_{1...j}$ .

2. Write down the recurrence that relates subproblems

If $S_{i}$ is not present in $T_{1...j}$ , then S_{i} itself is the shortest substring:

$D_{ij} = 1$

Otherwise, if $S_{i}$ is found at index k then we want the minimum result of either including it in the substring or not:

$D_{ij} = min(D_{i-1,j}, D_{i-1,k} + 1)$

3. Recognize and solve the base cases

The base cases are: $D_{i0} = 1, D_{0j} = 9999$ .

The first base case is for an empty string T. The second is for an empty string S. The value of 9999 is arbitrary, so long as it’s greater than the maximum possible length of T. It’s a marker to indicate that no solution is possible.

import java.util.Scanner;

class Main {

  static final int MAX = 9999;
  
  static int shortestSequence(char[] s, char[] t) {
    int m = s.length; 
    int n = t.length; 
    
    int dp[][] = new int[m+1][n+1]; 
  
    // String t is empty 
    for (int i = 0; i <= m; i++) 
        dp[i][0] = 1; 
  
    // String s is empty 
    for (int i = 0; i <= n; i++) 
        dp[0][i] = MAX; 
    
    for (int i = 1; i <= m; i++) 
    { 
        for (int j = 1; j <= n; j++) 
        { 
            char ch = s[i-1]; 
            int k; 
            for (k = j-1; k >= 0; k--) 
                if (t[k] == ch) 
                    break; 
  
            // char is not in t
            if (k == -1) 
              dp[i][j] = 1;
            else
               dp[i][j] = Math.min(dp[i-1][j], dp[i-1][k] + 1); 
        } 
    } 
  
    int ans = dp[m][n]; 
    if (ans >= MAX) 
        ans = -1; 
  
    return ans;
  }

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    char s[] = sc.next().toCharArray();
    char t[] = sc.next().toCharArray();

    System.out.println(shortestSequence(s, t));

    sc.close();
  }

}