Kody

Dany jest zbiór słów kodowych oraz tekst. Tekst zawiera komunikat złożony ze słów kodowych, umieszczonych w tekście w specjalny (być może niejednoznaczny) sposób.

Zarówno słowa kodowe, jak i tekst, są ciągami zbudowanymi tylko z wielkich i małych liter alfabetu angielskiego. Rozróżnienie wielkich i małych liter jest istotne. Długość słowa kodowego określa się w zwykły sposób. Na przykład słowo kodowe ALL ma długość 3.

Litery słowa kodowego nie musza występować w tekście kolejno po sobie. Np., słowo kodowe ALL zawsze występuje we fragmencie tekstu postaci AuLvL, gdzie u i v oznaczają dowolne (być może puste) ciągi kolejnych liter. O AuLvL mówimy, że jest pokryciem słowa ALL. W ogólności, pokryciem słowa kodowego nazywamy fragment tekstu, w którym pierwsza i ostatnia litera są takie same jak w słowie kodowym, a samo słowo możemy otrzymać przez usunięcie pewnych (być może żadnych) liter z tego fragmentu. Zauważmy, ze słowo kodowe może mieć wiele pokryć lub może ich nie mieć w ogóle. Podobnie, ten sam fragment tekstu może być pokryciem więcej niż jednego słowa kodowego.

Pokrycie opisujemy za pomocą pozycji jego początku (jego pierwszej litery) i końca (jego ostatniej litery) w tekście. (Pierwsza litera tekstu znajduje się na pozycji 1.) Mówimy, że pokrycia c₁ i c₂ nie zachodzą na siebie, gdy koniec c₂ znajduje się na wcześniejszej pozycji niż początek c₁, lub symetrycznie.

Aby odczytać ukryty w tekście komunikat masz znaleźć rozwiązanie. Rozwiązanie to zbiór elementów, z których każdy składa się ze słowa kodowego i jego pokrycia, spełniający następujące warunki:

1. pokrycia nie zachodzą na siebie parami,

2. długość żadnego pokrycia nie przekracza 1000,
3. łączna długość wystąpień słów kodowych jest maksymalna (licząc każde wystąpienie słowa kodowego w elemencie).

Założenia

• , gdzie N jest liczbą słów kodowych.
• Żadne słowo kodowe nie jest dłuższe niż 100.
• 1 długość tekstu 1 000 000.

Mówimy, że pokrycie c słowa kodowego w jest prawostronnie minimalne jeśli żaden właściwy prefiks (tzn. jego początkowy fragment, krótszy od niego samego) pokrycia c nie jest pokryciem w. Np., AAALAL jest prawostronnie minimalnym pokryciem słowa ALL, natomiast AAALALAL takim pokryciem nie jest. Tekst zawarty w danych wejściowych zawsze spełnia następujące warunki:

1. dla każdej pozycji w tekście liczba prawostronnie minimalnych pokryć, zawierających taką pozycję, nie przekracza 2500,
2. liczba prawostronnie minimalnych pokryć nie przekracza 10,000.

Wejście

Dane wejściowe są zawarte w dwóch plikach tekstowych: words.inp i text.inp. Plik words.inp zawiera listę słów kodowych, natomiast plik text.inp zawiera tekst wejściowy.

• Pierwszy wiersz pliku words.inp zawiera liczbę słów kodowych N. Każdy z kolejnych N wierszy zawiera po jednym słowie kodowym zapisanym jako ciąg liter, bez znaków odstępu między nimi. Słowa kodowe są ponumerowane od 1 do N zgodnie z porządkiem ich występowania w pliku words.inp.
• W pliku text.inp zapisano ciąg liter (zakończony znakami końca wiersza i końca pliku). Plik ten nie zawiera znaków odstępu.

Zaleca się deklarowanie plików wejściowych jako plików typu text, w odróżnieniu od plików znakowych (file of char).

Wyjście

Plikiem wyjściowym jest plik tekstowy codes.out.

• W pierwszym wierszu należy zapisać łączną długość wystąpień słów kodowych obliczoną przez Twój program.
• Każdy z kolejnych wierszy powinien zawierać opis jednego elementu Twojego rozwiązania. Wiersz taki zawiera trzy liczby całkowite i, s, e, gdzie i jest numerem słowa kodowego mającego pokrycie zaczynające się na pozycji s i kończącego się na pozycji e. Kolejność opisów elementów może być dowolna.

Przykład

words.inp:

4
RuN
RaBbit
HoBbit
StoP

text.inp:

StXRuYNvRuHoaBbvizXztNwRRuuNNP

codes.out:

12
2 9 21
1 4 7
1 24 28

(Uwaga: W tekście jest ukryty komunikat "RuN RaBbit RuN". (Ukryty jest tam również komunikat "RuN HoBbit RuN"). Pamiętaj, żeby nie wypisywać treści komunikatu do pliku wyjściowego.)

Ocena

Czas działania twojego programu nie może przekraczać 10 sekund. Nie można otrzymać części punktów za pojedynczy test.