给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。
# -*- 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))
联系客服