你不需要在我心目中的dp，但一个滑动窗口技术。string2的排列是长度完全相同且字符分布相同的字符串。在您的string2示例中，一个排列是。长度为3的字符串，字符分布如下：{a:1，b:1，c:1}。
因此，您可以编写一个脚本，从string1（index=0）开始考虑大小为n（string2的大小）的窗口。如果当前窗口具有完全相同的字符分布，则接受它作为排列，如果不接受，则不计算它，然后转到索引+1。
一个不重新计算每个滑动窗口中字符分布的技巧，你可以得到一个字符字典，并在第一个窗口计数字符，然后当你将窗口向右滑动一个时，你将删除字符减少1，将添加字符增加1。
代码应该是这样的，您需要对边缘情况进行验证：

def get_permut(string1,string2):
    N =len(string2)
    M = len(string1)

    if M < N:
        return 0

    valid_dist = dict()
    for ch in string2:
        valid_dist.setdefault(ch,0)
        valid_dist[ch]+=1

    current_dist=dict()
    for ch in string1[:N]:
        current_dist.setdefault(ch,0)
        current_dist[ch]+=1

    ct=0
    for i in range(M-N):
        if current_dist == valid_dist:
            ct+=1
        current_dist[i]-=1
        current_dist.setdefault(i+1,0)
        current_dist[i+1]+=1
        if current_dist[i]==0:
            del current_dist[i]

    return ct

您可以在这里使用string.count（）方法。请参见下面的解决方法：

import itertools
perms=[''.join(i) for i in itertools.permutations(string2)]

res=0

for i in perms:
    res+= string1.count(i)

print(res)

# 4

你可以用正则表达式。

def lst_permutation(text):
    from itertools import permutations
    lst_p=[]
    for i in permutations(text):
        lst_p.append(''.join(i))
    return lst_p

def total_permutation(string1,string2):
    import re
    total=0
    for i in lst_permutation(string2):
        res=re.findall(string2,string1)
        total += len(res)
    return total

string1 = 'abcdbcabdcabb'
string2 = 'cab'
print(total_permutation(string1,string2))

# 12

这里有一个愚蠢的方法来处理正则表达式（实际上不要这样做）。
对搜索文本中的每个字母使用非捕获组，然后期望每个捕获组中的一个出现在输出中：

import re

string1 = 'abcdbcabdcabb'
string2 = r'(?:c()|a()|b()){3}\1\2\3'

pos = 0
r = re.compile(string2)
while m := r.search(string1, pos=pos):
    print(m.group())
    pos = m.start() + 1

abc
bca
cab
cab

也可以动态生成

import re

string1 = 'abcdbcabdcabb'
string2 = 'cab'

before = "|".join([f"{l}()" for l in string2])
matches = "".join([f"\\{i + 1}" for i in range(len(string2))])
r = re.compile(f"(?:{before}){{{len(string2)}}}{matches}")

pos = 0
while m := r.search(string1, pos=pos):
    print(m.group())
    pos = m.start() + 1