Znajdź liczbę wystąpień podsekwencji w ciągu

Na przykład, niech ciąg będzie pierwszymi 10 cyframi liczby pi, 3141592653 , a podciąg będzie 123 . Zauważ, że sekwencja występuje dwukrotnie:

3141592653
 1    2  3
   1  2  3

To było pytanie z wywiadu, na które nie mogłem odpowiedzieć i nie mogę wymyślić wydajnego algorytmu, a to mnie niepokoi. Wydaje mi się, że powinno być możliwe wykonanie prostego wyrażenia regularnego, ale takie jak 1. * 2. * 3 nie zwracają wszystkich podciągów. Moja naiwna implementacja w Pythonie (policz 3 na każde 2 po każdym 1) działała przez godzinę i nie została wykonana.