Tira-jonot

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}$