Submission #74696728

---

Source Code Expand

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;

@SuppressWarnings("DuplicatedCode")
public class Main {
    static int MAX_STRING_LENGTH = (int) 1e6; // 字符串最大长度
    static int MAX_DIGIT_LENGTH = (int) 1e6; // 数位最大长度
    static int MOD7 = (int) 1e9 + 7, MOD8 = 80112002, MOD9 = 998244353, inf = Integer.MAX_VALUE;

    /***** 检查 T *****/
    static class Solution {

        void solve() {
            char[] s = io.nextCharArray(true), t = io.nextCharArray(true);
            int n = s.length, m = t.length;
            long ans = (long) n * (n + 1) / 2;
            int[][] f = new int[n + 1][m + 1];
            f[0][0] = 1;
            for (int i = 0; i < n; i++) {
                f[i + 1][0] = i + 2;
                for (int j = 0; j < m; j++) {
                    f[i + 1][j + 1] = s[i] == t[j] ? f[i][j] : f[i][j + 1];
                }
                ans -= f[i + 1][m];
            }
            io.println(ans);
        }


    }


    public static void main(String[] args) {
        io = new IO();
        int T = 1;
        // T = io.nextInt();
        for (; T > 0; T--) {
            new Solution().solve();
        }
        io.close();
    }

    static IO io;
    static class IO {
        BufferedInputStream bis = new BufferedInputStream(System.in);
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        int nextInt() {
            return (int) nextLong();
        }

        long nextLong() {
            try {
                long sign = 1, x = 0;
                int c = bis.read();
                while (c < '0' || c > '9') {
                    if (c == '-') sign = -1;
                    c = bis.read();
                }
                while (c >= '0' && c <= '9') {
                    x = x * 10 + (c - '0');
                    c = bis.read();
                }
                return sign * x;
            } catch (IOException e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                try {
                    int sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                try {
                    long sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        int[] nextDigitArray(int n) {
            try {
                int[] a = new int[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = x - '0';
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private int[] DIGIT_ARRAY;

        int[] nextDigitArray() {
            try {
                if (DIGIT_ARRAY == null) {
                    DIGIT_ARRAY = new int[MAX_DIGIT_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (!ignore(x)) {
                    DIGIT_ARRAY[m++] = x - '0';
                    x = bis.read();
                }
                int[] a = new int[m];
                System.arraycopy(DIGIT_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char nextChar() {
            try {
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                return (char) x;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        String[] nextStringArray(int n) {
            String[] a = new String[n];
            for (int i = 0; i < n; i++) {
                try {
                    if (CHAR_ARRAY == null) {
                        CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                    }
                    int x = bis.read();
                    while (ignore(x)) {
                        x = bis.read();
                    }
                    int m = 0;
                    while (x != ' ' && x != ',' && !ignore(x)) {
                        CHAR_ARRAY[m++] = (char) x;
                        x = bis.read();
                    }
                    a[i] = new String(CHAR_ARRAY, 0, m);
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        private char[] CHAR_ARRAY;

        char[] nextCharArray(boolean line) {
            try {
                if (CHAR_ARRAY == null) {
                    CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (line ? (x == ' ' || x == ',' || !ignore(x)) : !ignore(x)) {
                    CHAR_ARRAY[m++] = (char) x;
                    x = bis.read();
                }
                char[] a = new char[m];
                System.arraycopy(CHAR_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char[] nextCharArray(int n) {
            try {
                char[] a = new char[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = (char) x;
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private boolean ignore(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        String nextString(boolean line) {
            return new String(nextCharArray(line));
        }

        String nextString() {
            return nextString(false);
        }

        boolean nextBoolean() {
            return "true".equalsIgnoreCase(nextString());
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        void println(Object obj) {
            print(obj);
            print("\n");
        }

        void println() {
            print('\n');
        }

        void print(Object obj) {
            pw.print(obj);
        }

        void printf(String format, Object... obj) {
            pw.printf(format, obj);
        }

        void close() {
            try {
                if (bis != null) bis.close();
                if (pw != null) {
                    pw.flush();
                    pw.close();
                }
                bis = null;
                pw = null;
            } catch (Exception ignore) {
            }
        }
    }
}

Submission Info

Judge Result