| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_09_08 - Klasyka 1 |
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 składa się z małych liter alfabetu łacińskiego. Wzorzec składa się z małych liter alfabetu łacińskiego, ale może w nim wystąpić (co najwyżej jeden) symbol '?'. Uznajemy, że '?' dopasowuje się poprawnie do każdej litery.
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<=105) złożony z małych liter alfabetu łacińskiego,
- 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 co najwyżej jednego symbolu '?'.
Wyjście
Dla każdego zestawu testowego należy w osobnej linii wypisać liczbę wystąpień wzorca w tekście.
Przykład
Input: 3
aaaaabbb
ab
aaaaabbb
a?
aaaa
b Output: 1
5
0
| Dodane przez: | Damian Straszak |
| Data dodania: | 2013-07-31 |
| Limit czasu wykonania programu: | 1s-4s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU |
ukryj komentarze
|
2013-08-04 14:02:59 Damian Straszak
tak |
|
|
2013-08-04 13:33:00 Jacek Kozakiewicz
Czy dla testu: 1 asd sd? Poprawna odpowiedzia jest 0? |
|
|
2013-08-03 10:56:07 Damian Straszak
No ok, mój błąd. Możesz jeszcze się zrehabilitować i napisać szybsze ;) |
|
|
2013-08-03 10:52:41 Marcin Kasprowicz
Takie limity zasugerowały mi siłowe rozwiązanie ;) Ostatnio edytowany: 2013-08-03 10:55:24 |
|
|
2013-08-03 10:47:17 Damian Straszak
Przez moją pomyłkę w tym zadaniu były błędne limity czasowe. Zostały one poprawione. Jeden bezczelny AC zostanie zachowany ;) |
RSS