Cerinta completa

Given two strings, and , find and print the total number of ways to insert a character at any position in string such that the length of the Longest Common Subsequence of characters in the two strings increases by one.

Input Format

The first line contains a single string denoting .
The second line contains a single string denoting .

Constraints

Scoring

  • Strings and are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
  • The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).

Subtask

  • for of the maximum score.

Output Format

Print a single integer denoting the total number of ways to insert a character into string in such a way that the length of the longest common subsequence of and increases by one.

Sample Input

aa
baaa

Sample Output

4

Explanation

The longest common subsequence shared by and is aa, which has a length of . There are two ways that the length of the longest common subsequence can be increased to by adding a single character to :

  1. There are different positions in string where we could insert an additional a to create longest common subsequence aaa (i.e., at the beginning, middle, and end of the string).
  2. We can insert a b at the beginning of the string for a new longest common subsequence of baa.

As we have ways to insert an alphanumeric character into and increase the length of the longest common subsequence by one, we print on a new line.

Limbajul de programare folosit: java8

Cod:

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

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            if (c == -1) return null;
            StringBuilder sb = new StringBuilder();
            while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
            return sb.toString();
        }
    }

    static int idx(int i, int j, int cols) {
        return i * cols + j;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        String aStr = fs.next();
        String bStr = fs.next();

        int n = aStr.length();
        int m = bStr.length();
        int cols = m + 1;

        char[] a = aStr.toCharArray();
        char[] b = bStr.toCharArray();

        short[] pref = new short[(n + 1) * (m + 1)];
        short[] suf = new short[(n + 1) * (m + 1)];

        // Forward LCS DP
        for (int i = 1; i <= n; i++) {
            int row = i * cols;
            int prow = (i - 1) * cols;
            for (int j = 1; j <= m; j++) {
                short val;
                if (a[i - 1] == b[j - 1]) {
                    val = (short) (pref[prow + j - 1] + 1);
                } else {
                    short x = pref[prow + j];
                    short y = pref[row + j - 1];
                    val = (short) (x >= y ? x : y);
                }
                pref[row + j] = val;
            }
        }

        // Backward LCS DP (suffixes)
        for (int i = n - 1; i >= 0; i--) {
            int row = i * cols;
            int nrow = (i + 1) * cols;
            for (int j = m - 1; j >= 0; j--) {
                short val;
                if (a[i] == b[j]) {
                    val = (short) (suf[nrow + j + 1] + 1);
                } else {
                    short x = suf[nrow + j];
                    short y = suf[row + j + 1];
                    val = (short) (x >= y ? x : y);
                }
                suf[row + j] = val;
            }
        }

        int L = pref[idx(n, m, cols)];

        long ways = 0;
        boolean[] goodChar = new boolean[128];

        for (int i = 0; i <= n; i++) {
            Arrays.fill(goodChar, false);
            int row = i * cols;
            for (int j = 0; j < m; j++) {
                int left = pref[row + j];
                int right = suf[row + (j + 1)];
                if (left + right == L) {
                    goodChar[b[j]] = true;
                }
            }

            int cnt = 0;
            for (char c = '0'; c <= '9'; c++) if (goodChar[c]) cnt++;
            for (char c = 'A'; c <= 'Z'; c++) if (goodChar[c]) cnt++;
            for (char c = 'a'; c <= 'z'; c++) if (goodChar[c]) cnt++;
            ways += cnt;
        }

        System.out.println(ways);
    }
}

Scor obtinut: 1.0

Submission ID: 464619403

Link challenge: https://www.hackerrank.com/challenges/tutzki-and-lcs/problem

LCS Returns