루미 알고리즘

#1274플래티넘Rimord

PO 2004 결선코딩출제 Jimmy Mårdell, Håkan Strömberg, Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Du får givet en lång rad med n bokstäver, för enkelhetens skull valda bland A-Z. Genom att börja och sluta läsa raden på valfria ställen, kan du plocka ut ord, totalt (n(n+1))/2 stycken. Vi begränsar oss alltså inte till verkliga svenska ord utan accepterar vilken delsträng som helst av den givna raden som ett ord. Dock är vi endast intresserade av ord med ett bestämt antal, v, vokaler. Som vokaler räknar vi A, E, I, O, U, Y.

Din uppgift är att ta fram den största gruppen av sådana ord som alla rimmar på varandra. För att undvika missuppfattningar ger vi här en enkel definition på rim som förhoppningsvis stämmer någorlunda överens med ditt sätt att skriva vers. Två ord rimmar om de uppfyller följande tre villkor:

  • Båda orden ska innehålla minst en vokal.
  • Från och med första vokalen i varje ord och ända till slutet ska orden vara identiska. Det är alltså bara fram till första vokalen som orden får skija sig åt.
  • Orden får inte vara helt identiska.

Exempelvis rimmar SJUNGA och UNGA, VARG och KARG men inte till exempel VEDSTAPEL och KONSTAPEL, DRYG och ODRYG, TA och TA.

Notera om att ord_1 rimmar på ord_2 och ord_2 rimmar på ord_3 så rimmar automatiskt ord_1 på ord_3.

Indata

På första raden står ett heltal 1 ≤ 1 ≤ 10000 som anger hur många bokstäver den långa raden av bokstäver innehåller. På andra raden ett heltal v, 1 ≤ v ≤ 10, som anger hur många vokaler de bildade orden ska innehålla. På tredje och sista raden står en obruten följd av n bokstäver A...Z. Antalet vokaler bland dem är alltid större än v.

Utdata

Ett heltal som anger maximala antalet ord som

  • går att bilda från bokstavsföljden genom att börja och sluta läsa den på valfria ställen och
  • innehåller exakt v vokaler och
  • rimmar på varandra.

Orden får överlappa varandra i den ursprungliga följden och de får börja eller sluta på samma position i den ursprungliga följden, men observera att samma ord inte får räknas flera gånger.

예제

예제 1

입력
26
2
KVASTASTAHASTARMEDATTBASTA
출력
9

출처 표기

출처: Programmeringsolympiaden 2004년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.