COCI '17 Contest 1 #3 Lozinke Hard

View as PDF
Submit solution
Points: 7
Time limit: 3.0s
Memory limit: 128M
Problem type

Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.

Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if the user whose password is abc inputs one of the strings abc, abcd or imaabcnema, the system will successfully log him in, whereas the login will fail for axbc.

Mihael will be given 2 types of queries:

1 str: Insert str into the password database.

2 str: Output the number of users that can log into an account that has password str.

Input Specification

The first line will contain the positive integer Q (1 \le Q \le 100\,000), the number of queries.

The next Q lines will contain one of the above queries.

The passwords consist of at least one and at most 10 lowercase letters of the English alphabet.

Output Specification

For each type 2 query, output the number of users that can log into their accounts with str as the password.

Sample Input 1

5
1 aaa
2 aa
1 aa
2 aa
1 abb

Sample Output 1

1
2

Sample Input 2

4
1 x
1 x
1 xy
2 x

Sample Output 2

3

Sample Input 3

7
1 mir
1 mirta
1 ta
1 ir
1 t
2 t
2 mir

Sample Output 3

3
2

Comments


  • 0
    EZ_invictus  commented on July 16, 2024, 9:49 a.m.

    My code fails with WA at Batch #2 Case #1. Could i have that input, so i debug my code?


    • 0
      EZ_invictus  commented on July 16, 2024, 10:25 a.m.

      Not anymore needed, i debugged my code. C string library strcmp is not intuitive :(