Problem C
Sliding

Þér hafa borist gögn frá erfðafræðideild háskólans. Þeir biðja þig nú um að finna hvar í erfðamengi mýflugnanna sinna megi finna stökkbreytingu sem þeir eru að leitast eftir. Þar sem þessar mýflugur eru mjög erfðabreyttar koma 26 sýrur til greina í erfðamenginu frekar en bara fjórar, svo erfðamengið er gefið sem strengur af enskum lágstöfum. Stökkbreytingin sem verið er að leita að er einnig gefin sem strengur af enskum lágstöfum. Við segjum að stökkbreytingin $S$ komi fyrir í strengnum $T$ við staðsetningu $i$ ef stafur $i,i+1,\dots ,i+|S|-1$ í $T$ inniheldur sömu stafi og $S$, mögulega þó í annarri röð en í $S$. $|S|$ táknar hér lengd strengsins $S$.

Inntak

Fyrsta lína inntaksins inniheldur erfðamengi mýflugnanna $S$ og önnur lína inniheldur stökkbreytinguna $T$ sem verið er að leita að. Strengur $S$ er lengri en strengur $T$ og strengur $S$ er ekki lengri en ${10}^5$ bókstafir.

Úttak

Prentið allar staðsetningar í $S$ þar sem stökkbreytingin $T$ kemur fyrir.

abccba
bac

1
4