Tira-jonot

Tehtäväsi on laskea, moniko annetun merkkijonon osajono sisältää merkkijonon tira alijonona.

Merkkijono sisältää jonon tira alijonona silloin, kun merkkijonosta voidaan muodostaa merkkijono tira poistamalla siitä mahdollisesti osa merkeistä muuttamatta merkkien järjestystä. Esimerkiksi taikurinhattu sisältää sanan tira alijonona, mutta ritari ei sisällä.

Voit olettaa, että merkkijono muodostuu merkeistä a–z ja siinä on enintään $10^5$ merkkiä. Tavoitteena on, että algoritmin aikavaativuus on $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:

• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  
• tixratiyra
  

Huomaa, että kelvollinen osajono saa sisältää sanan tira alijonona myös useampia kertoja. Esimerkiksi sanasta tixratiyra voidaan lukea tira mm. tixratiyra tai tixratiyra