提出 #70615419

---

ソースコード 拡げる

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        
        int t = Integer.parseInt(br.readLine());
        
        while(t-- > 0) {
            String A = br.readLine().trim();
            String B = br.readLine().trim();
            
            pw.println(solve(A, B));
        }
        
        pw.close();
    }
    
    static int solve(String A, String B) {
        int n = A.length();
        
        // Check if same character frequencies
        int[] freqA = new int[2], freqB = new int[2];
        for(int i = 0; i < n; i++) {
            freqA[A.charAt(i) - '0']++;
            freqB[B.charAt(i) - '0']++;
        }
        if(freqA[0] != freqB[0]) return -1;
        
        // Use Z algorithm on B + "#" + A + A
        String s = B + "#" + A + A;
        int[] z = zFunction(s);
        
        // Look for matches at positions n+1 to 2n
        for(int i = n + 1; i < 2 * n + 1; i++) {
            if(z[i] == n) {
                return i - n - 1;
            }
        }
        
        return -1;
    }
    
    static int[] zFunction(String s) {
        int n = s.length();
        int[] z = new int[n];
        int l = 0, r = 0;
        
        for(int i = 1; i < n; i++) {
            if(i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }
            
            while(i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
                z[i]++;
            }
            
            if(i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        return z;
    }
}

提出情報

ジャッジ結果