루미 알고리즘

#1520플래티넘Stökiga känguruungar

PO 2021 온라인 예선코딩출제 Fredrik Ekholm, Simon Lindholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Ett känguruord (https://en.wikipedia.org/wiki/Kangaroo_word) är ett ord som bär på en synonym till sig självt (en “unge”), på så vis att alla synonymens bokstäver förekommer i ordet, i samma ordning. T.ex. är pastej ett känguruord, eftersom det bär på synonymen paj (pastej). Även aste och atj hade räknats som ungar om vi låtsas att de vore ord, men däremot inte paaj eller etsa. Formellt uttryckt måste ungen vara en subsekvens till ordet.

Vidare kan vi säga att en unge är stökig om den får plats i ordet på två olika sätt. paj är inte en stökig unge, men om ursprungsordet hade varit paastej hade den varit det – då hade den kunnat gömmas som antingen paastej eller paastej.

Givet ett (påhittat) ord S, och en lista med (påhittade) synonymer, hur många av synonymerna är stökiga ungar till S?

Indata

  • Den första raden innehåller en icke-tom sträng bestående av bokstäver a-z, ordet S som vi undrar över.
  • Den andra raden innehåller heltalet N (1 ≤ N ≤ 100000): antalet synonymer till ordet.
  • De följande N raderna innehåller synonymerna, vardera en icke-tom sträng bestående av bokstäver a-z.

Ingen synonym kommer förekomma två gånger, eller vara lika med S.

Låt M beteckna antalet bokstäver i S, och K summan av antalet bokstäver i synonymerna. Då gäller att M ≤ 100000, K ≤ 500000.

Utdata

Skriv ut ett heltal – antalet ord som är stökiga ungar till S.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeBegränsningar
120N, M, K ≤ 100.
220N, M ≤ 1000, och alla ungar är stökiga ungar.
320N, M ≤ 1000.
420Alla ungar är stökiga ungar.
520Inga ytterligare begränsningar.

Exempelfall

I exempel 1 är de första tre orden ungar till S, och dessutom stökiga. Testfallet skulle därmed kunna finnas med i testgrupp 2 eller 4.

I exempel 2 är de fyra första orden ungar, varav de två första dessutom stökiga ungar. Det här testfallet skulle inte kunna vara med i testgrupp 2 eller 4.

예제

예제 1

입력
paastej
5
paj
aste
atj
paaaj
etsa
출력
3

예제 2

입력
ababa
6
aa
aba
abb
baa
aabb
xyz
출력
2

출처 표기

출처: Programmeringsolympiaden 2021년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.