Competitive Programming: SPOJ – String 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] = 1;

// String s is empty
for (int i = 0; i <= n; i++)
dp[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();
}

}