Code Jam Kickstart 2018 Round F 题解

Problem A : Common Anagrams

 https://codejam.withgoogle.com/codejam/contest/3314486/dashboard#s=p0&a=0

/**
 * 2018 Round F
 *
 * Problem A. CommonAnagrams
 *
 * Ayla has two strings A and B, each of length L, and each of which is made of uppercase English alphabet letters.
 * She would like to know how many different substrings of A appear as anagrammatic substrings of B.
 * More formally, she wants the number of different ordered tuples (i, j), with 0 ≤ i ≤ j < L,
 * such that the i-th through j-th characters of A (inclusive) are the same multiset of characters as at least
 * one contiguous substring of length (j - i + 1) in B.
 *
 *
 * 题意：
 * 就是给定两个长度相同的字符串，找出在一个字符串中符合这样条件的所有子串：
 * 这些子串在另一个字符串中也以"异构词"（即字母和字母出现次数相同但位置可以不同）的形式出现；
 *
 * 解题思路：
 * 分别统计A中i-j的子串中每个字母出现的次数；然后再统计B中的，如果有相同的出现，则为符合条件的一个子串；
 * 使用buf[i][j][26]表示i-j的子串中26个字母出现的次数，相当于是将26个字母出现的情况转化为一个字符串，进行"序列化"了；
 */

     代码：

     

package CodeJam;

import java.io.*;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * 2018 Round F
 *
 * Problem A. CommonAnagrams
 *
 * Ayla has two strings A and B, each of length L, and each of which is made of uppercase English alphabet letters.
 * She would like to know how many different substrings of A appear as anagrammatic substrings of B.
 * More formally, she wants the number of different ordered tuples (i, j), with 0 ≤ i ≤ j < L,
 * such that the i-th through j-th characters of A (inclusive) are the same multiset of characters as at least
 * one contiguous substring of length (j - i + 1) in B.
 *
 *
 * 题意：
 * 就是给定两个长度相同的字符串，找出在一个字符串中符合这样条件的所有子串：
 * 这些子串在另一个字符串中也以"异构词"（即字母和字母出现次数相同但位置可以不同）的形式出现；
 *
 * 解题思路：
 * 分别统计A中i-j的子串中每个字母出现的次数；然后再统计B中的，如果有相同的出现，则为符合条件的一个子串；
 * 使用buf[i][j][26]表示i-j的子串中26个字母出现的次数，相当于是将26个字母出现的情况转化为一个字符串，进行"序列化"了；
 */

public class CommonAnagrams {

    public static void main(String[] args) {
        File input = new File("/Users/shaw/Downloads/A-small-practice.in");
        File output = new File("/Users/shaw/Downloads/A-small-practice.out");

        Scanner in = null;
        try {
            in = new Scanner(input);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        FileWriter printer = null;
        try {
            printer = new FileWriter(output);
        } catch (IOException e) {
            e.printStackTrace();
        }

        PrintWriter out = new PrintWriter(printer);

        int T = in.nextInt();

        for (int num = 1; num <= T; num++) {
            int L = in.nextInt();
            String A = in.next();
            String B = in.next();

            int[][][] buf = new int[L][L][26];  //记录i-j的子串中26个字母出现的情况
            Set<String> visited = new HashSet<>();  //用来记录出现过的26个字母出现的次数，组成的字符串

            for (int j = 0; j < L; j++) {
                int curChar = B.charAt(j) - 'A';
                for (int i = 0; i <= j; i++) {
                    if(i < j) buf[i][j] = buf[i][j - 1].clone();
                    else buf[i][j] = new int[26];
                    buf[i][j][curChar]++;
                    visited.add(toString(buf[i][j]));
                }
            }
            int res = 0;
            buf = new int[L][L][26];
            for (int j = 0; j < L; j++) {
                int curChar = A.charAt(j) - 'A';
                for (int i = 0; i <= j; i++) {
                    if(i < j) buf[i][j] = buf[i][j - 1].clone();
                    else buf[i][j] = new int[26];
                    buf[i][j][curChar]++;
                    if (visited.contains(toString(buf[i][j]))) res++;
                }
            }
            out.println("Case #" + num + ": " + res);
            System.out.println("Case #" + num + ": " + res);
        }

        in.close();
        out.close();
    }

    private static String toString(int[] count) {
        StringBuilder sb = new StringBuilder();
        for (int n : count) sb.append(n);
        return sb.toString();
    }

}