_spanningSubstring.java

public int spanningSubstring(String[] keywords, String paragraph) {
        String[] para = paragraph.split(" ");
        int len1 = keywords.length;
        int len2 = para.length;
        int res = Integer.MAX_VALUE;
        int[][] dp = new int[len1 + 1][len2 + 1];
        //dp(i, j) keyword end at ith word(included), match the paragraph ending at jth word(may or may not include), the rightmost left bound index in para
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = -1; // can not match
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (keywords[i - 1].equals(para[j - 1])) {
                    if (i == 1) {
                        dp[i][j] = j;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
                if (i == len1 && dp[i][j] != -1) {
                    res = Math.min(res, j - dp[i][j] + 1);
                }
            }
        }
        return res;
    }

SpanningSubstring.java

import org.junit.Test;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class SpanningSubstring {
    class InputValues {
        int n;
        String[] keywords;
        String paragraph;

        public InputValues(int n, String[] keywords, String paragraph) {
            this.n = n;
            this.keywords = keywords;
            this.paragraph = paragraph;
        }

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder();
            for (String keyword: keywords) {
                result.append(keyword).append("\n");
            }
            result.append(this.paragraph);
            return result.toString();
        }
    }

    @Test
    public void test() {
        File[] files = readFolder("src/input/SpanningSubstring");
        SpanningSubstring.InputValues test = readFile(files[1]);
        int res = spanningSubstring(test.keywords, test.paragraph);
        System.out.println(res);
    }

    @Test
    public void generateOutput() throws IOException {
        File[] files = readFolder("src/input/SpanningSubstring");
        for (int i = 0; i < files.length; i++) {
            File file = files[i];
            String outfileName = "src/output/SpanningSubstring/" + file.getName().replace(".in", ".out");
            File outfile = new File(outfileName);
            outfile.getParentFile().mkdirs();
            outfile.createNewFile();
            PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName));
            SpanningSubstring.InputValues test = readFile(file);
            int result = spanningSubstring(test.keywords, test.paragraph);
            printWriter.println(result);
            printWriter.close();
        }
    }

    public int spanningSubstring(String[] keywords, String paragraph) {
        String[] para = paragraph.split(" ");
        int len1 = keywords.length;
        int len2 = para.length;
        int res = Integer.MAX_VALUE;
        int[][] dp = new int[len1 + 1][len2 + 1];
        //dp(i, j) keyword end at ith word(included), match the paragraph ending at jth word(may or may not include), the rightmost left bound index in para
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = -1; // can not match
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (keywords[i - 1].equals(para[j - 1])) {
                    if (i == 1) {
                        dp[i][j] = j;
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
                if (i == len1 && dp[i][j] != -1) {
                    res = Math.min(res, j - dp[i][j] + 1);
                }
            }
        }
        return res;
    }

    private int getInt(String name) {
        return Integer.parseInt(name.replaceAll("\\D", ""));
    }

    private File[] readFolder(String path) {
        File folder = new File(path);
        File[] files = folder.listFiles();
        Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName()));
        return files;
    }

    private SpanningSubstring.InputValues readFile(File file) {
        try {
            // assume the input file is always valid
            Scanner sc = new Scanner(file);
            int n = Integer.parseInt(sc.nextLine().trim());
            List<String> keywords = new ArrayList<>();
            while(sc.hasNextLine() && keywords.size() < n){
                keywords.add(sc.nextLine());
            }
            String paragraph = sc.nextLine();
            sc.close();
            return new SpanningSubstring.InputValues(n, keywords.toArray(new String[keywords.size()]), paragraph);
        } catch (FileNotFoundException e) {
            System.out.println(file.getName() + " not exist");
        }
        return null;
    }

}