Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_09_09 - Klasyka 2 |
Do rozwiązania jest klasyczne zadanie. Dany jest tekst o długości n oraz wzorzec o długości m. Należy znaleźć liczbę wystąpień wzorca w tekście.
Tekst i wzorzec składają się z małych liter alfabetu łacińskiego. Dodatkowo w tekście i wzorcu może pojawić się pewna liczba symboli '?'. Uznajemy, że '?' dopasowuje się poprawnie do każdej litery (w tym do samego siebie).
Wejście
W pierwszej linii znajduje się liczba naturalna T (1<=T<=20) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
Pojedynczy zestaw testowy zbudowany jest następująco:
- w pierwszej linii zapisany jest tekst o długości n (1<=n<=5*105) złożony z małych liter alfabetu łacińskiego i symboli '?',
- w drugiej linii zapisany jest wzorzec o długości m (1<=m<=n) złożony z małych liter alfabetu łacińskiego i symboli '?'.
Wyjście
Dla każdego zestawu testowego należy w osobnej linii wypisać liczbę wystąpień wzorca w tekście.
Przykład
Input: 5
aaaaabbb
ab
aaaaabbb
a?
aaaa
b
?a?aab?b
ab
????????
a? Output: 1
5
0
3
7
Dodane przez: | Damian Straszak |
Data dodania: | 2013-07-31 |
Limit czasu wykonania programu: | 1s-23s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU |