Zjednodušené hledání v DNA

DNA je představována dlouhým řetězcem znaků, kde každý znak reprezentuje jednu aminokyselinu. Gen je představován kratším řetězcem znaků téže abecedy. Celá DNA prošla několika mutacemi. Při každé mutaci mohl (ale také nemusel) být zasažen i gen, který budeme v DNA hledat.

Pro naši analýzu bude jedna mutace DNA znamenat, že z jejího kódu buďto vypadne kterýkoli znak abecedy nebo naopak jeden znak abecedy kdekoli přibyde. Může přibýt i na úplném začátku nebo konci. Neuvažujeme možnost, že by se během jedné mutace přepsal jeden znak na jiný.

Úloha

Je dán určitý gen G a chceme vědět, zda se v DNA vyskytoval před jejími mutacemi. Mutacemi mohlo dojít i k tomu, že v DNA vznikl podřetězec podobný G přestože původně v tom místě DNA gen G nebyl. Takový podřetězec nedokážeme odlišit od mutovaného genu G. Proto je úloha formulována tak, že máme najít všechna místa v mutované DNA, kde se původně G mohl vyskytovat. Předpokládejme, že DNA prošla k (k ≥ 0) mutacemi. Původní podobu DNA neznáme, známe jen její mutovanou podobu, označme ji DNAm. Řekneme, že pozice p v DNAm je možným výskytem G, pokud lze G nejvýše k mutacemi změnit na mutovaný gen Gm délky d tak, že úsek DNAm na pozicích p−d+1 .. p se shoduje s Gm. Různé exempláře DNA mají různý počet mutací k. Pozice v DNA pro jednoduchost zpracování číslujeme od 0.

Vstup

Vstupní data jsou zapsána v textovém souboru na jednotlivých řádcích takto:

• 1. ř.: Abeceda, v níž jsou i DNAm i hledaný gen G zapsány. Je to jediný řetězec bez mezer, mezera není nikdy prvkem abecedy. Na pořadí znaků zde nezáleží.
• 2. ř.: Kód hledaného genu G v původní nezmutované podobě. Je to jediný řetězec bez mezer.
• 3. ř.: Počet mutací k, kterými DNAm prošla. Je to celé číslo z intervalu <0, 2000>.
• 4. ř.: Kód DNAm po k mutacích. Je to jediný řetězec bez mezer.

Každý řádek je ukončen znakem konce řádku, řádky neobsahují žádné počáteční mezery.

Výstup

Výstupem je textový soubor obsahující ve vzestupném uspořádání všechny možné pozice výskytu daného genu v dané DNAm. Každá pozice je uvedena na samostatném řádku bez úvodních mezer.

Příklad 1:

abcde
abcd
2
ecdcaabdcbcdccba

2
6
7
8
10
11
12

Příklad 1:

abc
aaaaaaa
3
aaabcaaaabcaabc

7
8
9
12

K dispozici jsou data rozsahem a složitostí velmi podobná ostrým testovacím datům. Poskytujeme je zde pro ladící pohodlí laskavých řešitelů.
Data