KMP Algorithm

题号：NC210589
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

We define the mismatch function mis(s,t) of two string $s_1s_2\dots s_n$ and $t_1 t_2 \dots t_n$ as the number of indices i such that $s_i\neq t_i$ .
A string $s_1s_1\dots s_n$ is called nearly d-periodic, iff $mis(s_1s_2\dots s_{n-d}, s_{d+1}s_{d+2}\dots s_n)\leq d$ .
You are given two strings s,t, which are both nearly d-periodic. The lengths of s and t are n and m respectively. Compute $mis(s_{i}s_{i+1}\dots s_{i+m-1}, t_1t_2\dots t_m)$ for all $i (1\leq i\leq n-m+1)$ .

输入描述:

The first line contains an integer .
The second line contains a lowercase string . The third line contains a lowercase string .

输出描述:

Output |s|-|t|+1 line. Each line contains an integer - the answer for .

示例1

输入

复制

2
abaaabab
abab

输出

复制