All Tracks Data Structures Advanced Data Structures Suffix Arrays Problem

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++, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?