AtCoder Beginner Contest 430 E

https://atcoder.jp/contests/abc430/tasks/abc430_e

1個ずらしでタイリングするとよいです。すなわち、

元の文字列 -----------------------------
           -----
            -----
             -----
                           ...
                                   -----

みたいに切り出します。ただし、今回は右端まで行ったら、左に戻ってくるようにします。そして、それを2進で整数にします。100なら100→010→001だから、4→2→1となります。
そうすると両方の文字列でその整数が共通するはずなので、それを手掛かりにいくつずれなのかの候補を出して、最後に片方の文字列をずらせばちゃんと合っているかを調べます。

// Shift String
#![allow(non_snake_case)]

use std::cmp::min;
use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}


//////////////////// process ////////////////////

fn bit(c: char) -> u64 {
    ((c as u8) - ('0' as u8)) as u64
}

fn ones(L: usize) -> u64 {
    if L == 0 {
        0
    }
    else if L >= 64 {
        u64::MAX
    }
    else {
        (1u64 << L) - 1
    }
}

fn tile(S: String, L: usize) -> Vec<u64> {
    let N = S.len();
    let cs: Vec<char> = S.chars().collect();
    let mut v: Vec<u64> = vec![0; N];
    for i in 0..L {
        let b = bit(cs[i]);
        v[0] = (v[0] << 1) | b
    }
    
    let mask = ones(L);
    for p in 1..N {
        let q = if p + L - 1 < N { p + L - 1 } else { p + L - 1 - N };
        v[p] = ((v[p-1] << 1) & mask) | bit(cs[q])
    }
    v
}

// 要素がある場所
fn count(v: &Vec<u64>) -> Vec<(u64, Vec<usize>)> {
    let mut counter: HashMap<u64, Vec<usize>> = HashMap::new();
    for (p, &n) in v.iter().enumerate() {
        let e = counter.entry(n).or_insert(vec![]);
        (*e).push(p)
    }
    let mut w: Vec<(u64, Vec<usize>)> = counter.into_iter().collect();
    w.sort_by_key(|(n, ps)| (ps.len(), *n));
    w
}

fn find_value(n: u64, c: &Vec<(u64, Vec<usize>)>) -> Option<Vec<usize>> {
    c.iter().filter(|(n1, _)| *n1 == n).map(|(_, v)| v.clone()).next()
}

// 短い順にして返す
fn find_diffs(p1: usize, ps2: &Vec<usize>, N: usize) -> Vec<usize> {
    let L = ps2.len();
    let mut v: Vec<usize> = vec![];
    let i_ = (0..L).rev().filter(|&i| ps2[i] <= p1).next();
    if let Some(i) = i_ {
        for j in (0..i+1).rev() {
            v.push(p1 - ps2[j])
        }
        for j in (i+1..L).rev() {
            v.push(N + p1 - ps2[j])
        }
    }
    else {
        for j in (0..L).rev() {
            v.push(N + p1 - ps2[j])
        }
    }
    v
}

fn is_same(diff: usize, tiles1: &Vec<u64>, tiles2: &Vec<u64>) -> bool {
    let N = tiles1.len();
    let L = min(64, N);
    for p1 in (0..N).step_by(L) {
        let p2 = if p1 >= diff { p1 - diff } else { N + p1 - diff };
        if tiles1[p1] != tiles2[p2] {
            return false
        }
    }
    true
}

fn F_each(A: String, B: String) -> i32 {
    let N = A.len();
    let L = min(64, N);
    let tiles1 = tile(A, L);
    let tiles2 = tile(B, L);
    let counter1 = count(&tiles1);
    let counter2 = count(&tiles2);
    if counter1.len() != counter2.len() {
        return -1
    }
    else if counter1.len() == 1 {
        return if counter1[0].0 == counter2[0].0 { 0 } else { -1 }
    }
    
    let (n1, ps1) = &counter1[0];
    let ps2_wrapped = find_value(*n1, &counter2);
    if ps2_wrapped.is_none() {
        return -1
    }
    let ps2 = ps2_wrapped.unwrap();
    if ps1.len() != ps2.len() {
        return -1
    }
    
    let p1 = ps1[0];
    let diffs = find_diffs(p1, &ps2, N);
    for diff in diffs {
        if is_same(diff, &tiles1, &tiles2) {
            return diff as i32
        }
    }
    -1
}

fn F(T: usize) {
    for _ in 0..T {
        let A: String = read();
        let B: String = read();
        println!("{}", F_each(A, B))
    }
}

fn main() {
    let T: usize = read();
    F(T)
}