One mismatch
Tag(s):

## Data Structures, Data Structures, Hard, Suffix array, Suffix array

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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, 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