One mismatch
Tag(s):

## Data Structures, Hard

Problem
Editorial
Analytics

Given a string $s$ and a set of $n$ strings $p_i$.

For each $i$ find the number of occurrences of $p_i$ in $s$ with at most one $k$-length gap.

The string $s$ occurs in string $t$ at position $p$ with at most one $k$-length gap if strings $s$ and $t_pt_{p+1}\ldots t_{p+|s|-1}$ are equal with at most one $k$-length gap.

Strings $s$ and $r$ are equal with at most one $k$-length gap if:

1. $|s| = |r|$;
2. or all $i$ and $j$ such that $s_i \ne r_i$ and $s_j \ne r_j$, it holds $|i - j| < k$.

Input format

First line of input contains single integer $k$ ($1 \leq k \leq 2 \cdot 10^5$).

Second line of input contains string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$).

Third line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

Then follow $n$ lines. The $i$-th of them contains string $p_i$ ($\sum\limits_{i=1}^{n} |p_{i}| \leq 2 \cdot 10^5$).

$s$ and $p_i$ can contain characters with codes from $33$ to $126$, inclusive.

Output format

Print $n$ lines. The $i$-th of them should contain the number of occurrences $p_i$ in $s$ with at most one $k$-length gap.

SAMPLE INPUT
1
abc
3
ac
b
acb
SAMPLE OUTPUT
2
3
0
Explanation
• "ac" equals "ab" and "bc"
• "b" equals "a", "b" and "c"
• "acb" doesn't equal "abc"
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > Graphs