[[problem:FANMEETING]]

다음과 같은 두가지 방법으로 풀어보았는데 둘 다 시간초과가 뜹니다.

다음 코드는 카라츠바 알고리즘을 사용한 풀이입니다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int caseN = in.nextInt();
        String idol;
        String fan;
        BigInteger idols;
        BigInteger fans;
        int count;
        for (int i = 0; i < caseN; i++) {
            idol = in.next();
            fan = in.next();
            count = 0;
            idol = idol.replaceAll("F", "0");
            idol = idol.replaceAll("M", "1");
            fan = fan.replaceAll("F",  "0");
            fan = fan.replaceAll("M", "1");
            idols = new BigInteger(idol);
            fans = new BigInteger(fan);
            idols = karatsuba(idols, fans);
            String zeros = "";
            for (int k = idols.toString().length(); k < fan.length(); k++) {
                zeros = zeros + "0";
            }
            zeros = zeros + idols.toString();
            for (int j = idol.length() - 1; j < fan.length() ; j++) {
                if (zeros.charAt(j) == '0')
                    count++;
            }
            System.out.println(count);
        }
    }
    public static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute sub-expressions
        BigInteger ac    = karatsuba(a, c);
        BigInteger bd    = karatsuba(b, d);
        BigInteger abcd  = karatsuba(a.add(b), c.add(d));

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
    }
}

다음은 비트마스킹을 이용한 방법입니다.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int caseN = in.nextInt();
        String idol;
        String fan;
        BigInteger idols;
        BigInteger fans;
        int count;
        for (int i = 0; i < caseN; i++) {
            idol = in.next();
            fan = in.next();
            count = 0;
            idol = idol.replaceAll("F", "0");
            idol = idol.replaceAll("M", "1");
            fan = fan.replaceAll("F", "0");
            fan = fan.replaceAll("M", "1");
            idols = new BigInteger(idol,2);
            for(int j = 0; j < fan.length() - idol.length() + 1; j++){
                fans = new BigInteger(fan.substring(j, j+idol.length()),2);
                
                if (idols.and(fans).compareTo(BigInteger.ZERO) == 0)
                    count++;
            }
            System.out.println(count);
        }
    }
}

idol을 고정시키고 fan 전체를 맞물리게 이동시키면서 and연산 하여
(남자는 1, 여자는 0) 결과가 0일 때만 카운트를 세어 출력하도록
했습니다.

여기서 막혀서 이틀째 고생중인데 도와주세요..

하나 더 질문드리면 책에 있는 카라츠바 알고리즘 코드에서
b의 자릿수가 half보다 작을 때 b0가 b가 되어야 하는 것 아닌가요?