Ալգորիթմներ և Տվյալների Կառուցվածքներ

Պրեֆիքսային որոնում

Ձեզ տրվում է բառարան (dictionary), որը նախապես դատարկ է: Դուք պետք է մշակեք մի շարք հարցումներ, որոնք բաժանվում են երկու տարբեր տիպի.
  1. Տիպ 1 հարցում: Բառ ավելացնել բառարան
      • Input: 1 word (1 ≤ |word| ≤ 1000), where word is a non-empty string consisting of lowercase English letters.
      • Action: Add the word to the dictionary.
  1. Տիպ 2 հարցում: Հաշվել, թե քանի բառ է սկսվում տրված պրեֆիքսով
      • Input: 2 prefix (1 ≤ |prefix| ≤ 1000), where prefix is a non-empty string consisting of lowercase English letters.
      • Output: Output the number of words in the dictionary that start with the given prefix.
- Մուտք: 2 prefix (1 ≤ |prefix| ≤ 1000), որտեղ prefix-ը նույնպես դատարկ չէ և բաղկացած է անգլերեն փոքրատառ տառերից

Μուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000), որը ցույց է տալիս հարցումների քանակը:
Հաջորդ n տողերում տրված են հարցումները, և յուրաքանչյուր տող գալիս է հետևյալ ձևերից մեկով.
  • 1 word (Տիպ 1 հարցում)
  • 2 prefix (Տիպ 2 հարցում)
Երաշխավորված է, որ մուտքում ընդհանուր սիմվոլների քանակը չի գերազանցում -ը:

Ելք

Յուրաքանչյուր Տիպ 2 հարցման համար պետք է տպել մեկ ամբողջ թիվ առանձին տողում, որը ցույց է տալիս, թե քանի բառ է սկսվում տվյալ պրեֆիքսով:

Օրինակներ

Մուտք
Ելք
7 1 aba 1 abac 1 caba 2 ab 1 caba 1 cd 2 c
2 3

Constraints

Time limit: 7 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue