COCI '14 Contest 5 #6 Divljak

View as PDF

Submit solution

Points:40 (partial)
Time limit:4.0s
Memory limit:1G

Problem types

Nowadays, there are a lot of unusual people. We won't go into details, but instead focus on a certain type, to us personally the most interesting people. Of course, we're talking about barbarians!

There are a lot of barbarians, but only a few of them are truly important. This story has N important barbarians, denoted with integers from 1 to N. Each of them has their own stone tablet with their word written on it, consisting of only lowercase letters of the English alphabet.

Our barbarians are playing an interesting game with their good friend Tarzan. The game is played in Q rounds. There are two round types and each is determined by Tarzan:

  • 1^{st} type: Tarzan shows the word P to the barbarians.
  • 2^{nd} type: Tarzan asks the barbarian denoted with S the following question: "Out of all the words I've shown you so far, how many of them are such that the word on your stone tablet is their consecutive substring?"

Given the fact that the barbarians go wild a lot and aren't really able to pay attention and keep up with what's happening in the game, they need your help. Help the barbarians answer each of Tarzan's questions correctly.


The first line of input contains the integer N (1 \le N \le 10^5), the number of barbarians.

Each of the following N lines contains a single word consisting of only lowercase letters of the English alphabet, the i^{th} word corresponding to the word on the stone tablet of barbarian denoted with i.

After that, the integer Q (1 \le Q \le 10^5) follows, the number of rounds in the game. The following Q lines describe the round of the game, the i^{th} line describing the i^{th} round of the game. Each line will contain the integer O. In the case when O is equal to 1, it denotes the first type of round and the shown word P follows in the same line, consisting of only lowercase letters of the English alphabet.

In the case when O is equal to 2, it denotes the second type of round and the number S (1 \le S \le N) follows in the same line, the label of the barbarian whom Tarzan asked the question.

The total length of all words written on the barbarians' stone tablets will not exceed 2 \cdot 10^6.

The total length of all words that Tarzan shows the barbarians will not exceed 2 \cdot 10^6.


For each round of a different form, output a single line. The i^{th} line must contain the correct answer to Tarzan's question in the i^{th} round of type 2.


In test cases worth 50% of total points, it will hold N \le 20\,000.

Sample Input 1

1 abca
2 1
2 3

Sample Output 1


Explanation for Sample Output 1

The only word Tarzan has shown is abca. The answer to the first question is, of course, 1 because the word a is a substring of the word abca. The answer to the second question is also 1 because the word abc is a substring of the word abca.

Sample Input 2

1 aaabbabbaab
2 7
1 baabaaa
1 aabbbab
2 3
1 aabba
2 3

Sample Output 2



  • 3
     commented on Sept. 11, 2017

    After some investigation, I'm now completely sure that test data is wrong. Every testdata has a pattern of

    1 aaaaaaaa 2 1 aaaaaaaaa 2 1

    However, printing one integer 0 or 1 doesn't give any scores, while it's the only candidate for answer. I suspect that input datas are somehow flawed and replaced into one single weird file.

    • 2
       commented on Sept. 11, 2017

      Issue has been resolved. Will rejudge submissions shortly.

  • 4
     commented on Aug. 26, 2017

    Hello! I'm facing several issues while solving this problem, can you please check it?

    1) My code which gets AC on other judge gots WA here for every case I can check. (

    2) I submitted the official code from (sorry to do this, but I wasn't able to understand the judge at all :/), with assert(n <= 10000) to avoid ACs. It also gets TLE on every cases I can check.

    3) I submitted the code which is basically cin >> n, assert(n == 1). It don't get RTE, but gets WA. for every cases I can check.

    By "every cases I can check" I meant the first TCs in batch test.