InternDoor

Every place a pattern appears

Mediumstrings · string matchingRead the input, print the output

Reported in interviews at (where)

For each test you are given a text and a pattern, both lowercase letters. Count the positions in the text where the pattern starts, letter for letter. Appearances may overlap: in aaaa the pattern aa appears 3 times.

Comparing the pattern at every position costs O(n m), too slow when both are long. Aim for O(n + m).

Input

The first line holds T, the number of tests. Each test is two lines: the text, then the pattern.

Output

For each test, one line: how many times its pattern appears in its text.

Example
Input
3
aaaa
aa
banana
ana
abc
abcd
Output
3
2
0
  1. aa starts at the first, second and third letter.
  2. The two appearances share the middle a.
  3. A pattern longer than the text cannot appear in it.

Limits

  • 1 <= T <= 100
  • the text and the pattern each hold 1 to 100000 letters
  • all the texts and patterns together hold at most 400000 letters

Hints

Hint 1

When a comparison fails part way, the letters you already matched tell you where the next possible match can start: you never need to look at a text letter twice.

Hint 2

Precompute, for each prefix of the pattern, its longest proper prefix that is also its suffix (the KMP failure function), or run the Z-algorithm on pattern + separator + text.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.