use std::fs::File;
use std::io::{BufRead, BufReader, BufWriter, Write};

const TASK_NAME: &str = "strmatch";

fn compute_pi(string: &[char]) -> Vec<i32> {
    let n = string.len();
    let mut pi: Vec<i32> = vec![-1; n + 1];
    for i in 0..n {
        let mut j = pi[i];
        while j != -1 && string[i] != string[j as usize] {
            j = pi[j as usize];
        }
        pi[i + 1] = j + 1;
    }
    pi
}

fn apply_kmp(pattern: &str, text: &str) -> Vec<usize> {
    let pattern = pattern.chars().collect::<Vec<char>>();
    let pi = compute_pi(&pattern);
    let mut j = 0;
    let mut solution = Vec::new();
    for (i, c) in text.chars().enumerate() {
        while j != -1 && c != pattern[j as usize] {
            j = pi[j as usize];
        }
        j += 1;
        if j as usize == pattern.len() {
            solution.push(i - pattern.len());
            j = pi[j as usize];
        }
    }
    solution
}

fn main() {
    let input: Vec<String> =
        BufReader::new(File::open(format!("{}.in", TASK_NAME).as_str()).expect("input file"))
            .lines()
            .map(|line| line.unwrap())
            .collect();
    let mut output_file =
        BufWriter::new(File::create(format!("{}.out", TASK_NAME).as_str()).expect("output file"));

    let matches = apply_kmp(&input[0], &input[1]);
    
    writeln!(
        output_file,
        "{}\n{}",
        matches.len(),
        matches
            .iter()
            .take(1000)
            .map(|pos| format!("{}", pos + 1))
            .collect::<Vec<String>>()
            .join(" ")
    )
    .expect("output write");
}