给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

        a. S "babgbag"->T "bag"，出现5次。

哪5次？

# -*- coding: utf-8 -*-

"""

Created on Sun Jun 14 09:45:57 2020

@author: Lijie Wang

"""

#coding=utf-8

import sys 

State=[]

Time=0

def f(N,S,T):

    global State

    if N==1:

        for i in range(len(S)):

            if T[N-1] == S[i]:

                State.append(i)

        #print(N-1,State)

        f(N+1,S,T)

    elif N <= len(T):

        if(N==len(T)+1):

            return State

        State1=[]

        temp = []

        for i in range(len(S)):

                if T[N-1]==S[i]:

                    temp.append(i)

        num = 0

        for m in State:

                for n in temp:

                    if m < n:

                        #print(m,n)

                        State1.append(n)

                        num=num+1

        State=State1

        #print(N,State)

        f(N+1,S,T)

S= "babgbag"

T="bag"

f(1,S,T)

print(len(State))