Tehtäväsi on laskea, moniko annetun merkkijonon osajono sisältää merkkijonon tira alijonona.
\newcommand{\T}{\texttt} \newcommand{\U}[1]{\underline{\smash{\T{#1}}}}
Merkkijono sisältää jonon tira alijonona silloin, kun merkkijonosta voidaan muodostaa merkkijono tira poistamalla siitä mahdollisesti osa merkeistä muuttamatta merkkien järjestystä. Esimerkiksi \U{t}\T{a}\U{i}\T{ku}\U{r}\T{inh}\U{a}\T{ttu} sisältää sanan tira alijonona, mutta \T{ritari} ei sisällä.
Algoritmin aikavaativuuden tulee olla O(n).
Toteuta tiedostoon sequences.py funktio count, joka palauttaa sellaisten osajonojen määrän, joilla on tira alijonona.
def count(s):
# TODO
if __name__ == "__main__":
print(count("ritari")) # 0
print(count("taikurinhattu")) # 4
print(count("ttiirraa")) # # 4
print(count("tixratiyra")) # 11
print(count("aotiatraorirratap")) # 42
Selitys: Esimerkiksi merkkijonossa tixratiyra on 11 osajonoa, jotka sisältävät jonon tira alijonona:
- \U{tixratiyra}
- \U{tixratiyr}\T{a}
- \U{tixratiy}\T{ra}
- \U{tixrati}\T{yra}
- \U{tixrat}\T{iyra}
- \U{tixra}\T{tiyra}
- \T{tixra}\U{tiyra}
- \T{tixr}\U{atiyra}
- \T{tix}\U{ratiyra}
- \T{ti}\U{xratiyra}
- \T{t}\U{ixratiyra}
Huomaa, että kelvollinen osajono saa sisältää sanan tira alijonona myös useampia kertoja. Esimerkiksi sanasta tixratiyra voidaan lukea tira mm. \U{ti}\T{xratiy}\U{ra} tai \U{ti}\T{x}\U{r}\T{atiyr}\U{a}