【python吉比特】字符串距离？

题目：给出两个相同长度的由字符 a 和 b 构成的字符串，定义它们的距离为对应位置不同的字符 的数量。如串”aab”与串”aba”的距离为 2;串”ba”与串”aa”的距离为 1;串”baa”和串”baa”的 距离为 0。下面给出两个字符串 S 与 T，其中 S 的长度不小于 T 的长度。我们用|S|代表 S 的 长度，|T|代表 T 的长度，那么在 S 中一共有|S|-|T|+1 个与 T 长度相同的子串，现在你需要计 算 T 串与这些|S|-|T|+1 个子串的距离的和。

输入描述:

第一行包含一个字符串 S。

第二行包含一个字符串 T。

S和T均由字符a和b组成，1≤ |T| ≤ |S| ≤105。

输出描述:

输出对应的答案。

示例1

输入

aab

aba

输出

2

说明

示例2

输入

aaabb

bab

输出

5

说明

在样例 2 中，”aaa”与”bab”的距离为 2，”aab”与”bab”的距离为 1，”abb”与”bab”的距离为 2，

所以最后答案为 5。

code：

###两个循环会超时###扫描思想：例如s=aaabb，t=bab

###1.先看t中的第一个字符b在s中扫过s=[0:3]=aaa 所以有三次不同

###2.再看t中的第二个字符a在s中扫过s=[1:4]=aab 所以有一次不同

###3.再看t中的第三个字符b在s中扫过s=[2:5]=abb 所以有一次不同

###所以总共有五次不同

###建立a[i]代表s中s[:i]中a的个数，那么b的个数就是i-s[:i]

s = 'aaabb'#input()

t = 'bab'#input()

a = [0]

for i in range(len(s)):

    if s[i] == 'a':

        a.append(a[-1] + 1)

    else:

        a.append(a[-1])

res = 0

delta = len(s) - len(t) + 1

for j in range(len(t)):

    if t[j] == 'a':

        res += j + delta - a[j + delta] - (j - a[j])

    else:

        res += a[j + delta] - a[j]

print(res)