字符串距离

#include <bits/stdc++.h>
using namespace std;

int main(){
    string S, T;
    cin>>S>>T;
    long n=S.length(), m=T.length(), sum=0, k=0, cnt_a=0, cnt_b=0;
    for(int i=0;i<n;i++){
        if(i<m){
            if(T[i]=='a')
                cnt_a++;
            else
                cnt_b++;
        }
        if(S[i]=='a')
            sum += cnt_b;
        else
            sum += cnt_a;
        if(i>=n-m){
            if(T[k++]=='a')
                cnt_a--;
            else
                cnt_b--;
        }
    }
    printf("%ld\n", sum);
    return 0;
}

//注意要用long long
#include <iostream>

using namespace std;

int main(){
    string s1, s2;
    cin >> s1;
    cin >> s2;
    long long numa, numb, total, pos;
    numa = numb = total = pos = 0;
    for (int i=0; i<s1.length(); ++i){
        if (i<s2.length()){
            if (s2[i] == 'a') numa++;
            else numb++;
        }
        if (s1[i] == 'a') total += numb;
        else total += numa;
        if (i>=s1.length() - s2.length()){
            if (s2[pos++] == 'a') numa--;
            else numb--;
        }
    }
    
    cout << total;
    
}

字符串T的第i个字符在字符串S的比较区间为S[i:i+|S|-|T|],因此对于每个字符T[i],只需
统计S[i:i+|S|-|T|]中与T[i]不同的个数即可。用前缀和preSum[i]表示字符串S前i个元素
中a的个数可优化求解。

#include <cstdio>
#include <vector>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    string S, T;
    cin >> S >> T;
    int m = S.length(), n = T.length();
    vector<int> preSum(m, 0);  // preSum[i]表示前i个元素中a的个数
    preSum[0] = S[0]=='a'?1:0;
    for (int i = 1; i < m; ++i)
        preSum[i] = S[i]=='a'?preSum[i-1]+1:preSum[i-1];
    long ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int num = preSum[i+m-n]-(i>0?preSum[i-1]:0);
        if (T[i]=='a')
            ans += m-n+1-num;
        else 
            ans += num;
    }
    printf("%ld\n", ans);

    return 0;
}

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
 /*
 T中第i各元素会和S中[i, n-m]区间内的字符进行比较
 通过对T中每一个元素分类讨论，查看为相同字符的个数
 用所有比较次数减去相同的个数则为结果
 
 */
	string s1, s2;
	LL ans = 0;
	cin >> s1 >> s2;
	LL n = s1.size(), m = s2.size();
	vector<LL>arr(n + 1, 0);//关于a个数 的前缀数组
	for (LL i = 0; i < n; i++)
	{
		arr[i + 1] = arr[i] + (s1[i] == 'a');
	}
	for (LL i = 0; i < m; i++)
	{
		if (s2[i] == 'a')
			ans += arr[n - m + 1 + i] - arr[i];
		else
			ans += n-m+1-(arr[n - m + 1 + i] - arr[i]);
	}
	cout <<m*(n-m+1)- ans << endl;
}
/*

*/

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        System.out.println(solve(s, t));
    }
    private static long solve(String s, String t) {
        int dis = s.length() - t.length() + 1;
        long[] a = new long[s.length() + 1];
        for (int i = 1; i <= s.length(); i++) {
            a[i] = s.charAt(i - 1) == 'a' ? a[i - 1] + 1 : a[i - 1];
        }
        long res = 0;
        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == 'a') {
                res += (i + dis - a[i + dis]) - (i - a[i]);
            } else {
                res += a[i + dis] - a[i];
            }
        }
        return res;
    }
}

	#include<string>



	#include<iostream>



	#include<stdio.h>



	using namespace std;



	int dis(string s,string t){



	    int n = s.length();



	    int num=0;



	    for(int i=0;i<n;i++){



	        if(s[i] != t[i]){



	            num++;



	        }



	    }



	    return num;



	}



	int main(){



	    string s,t;



	    while(cin>>s>>t){



	        int ls = s.length();



	        int lt = t.length();



	        int sum=0;



	        for(int i=0;i<=ls-lt;i++){



	            string zc=s.substr(i,lt);



	            int distance = dis(t,zc);



	            sum+=distance;



	        }



	        printf("%d",sum);



	        continue;



	    }



	    return 0;



	}

###两个循环会超时
###扫描思想：例如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=input()
t=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)

/** 您的代码已保存 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。 case通过率为80.00% 有人能告诉我这是什么问题吗？？？
*/
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext())
        {
            String a  = scanner.nextLine();
            String b = scanner.nextLine();
            System.out.println(stringDistance(a,b));
        }
    }

    public static int stringDistance(String a, String b)
    {
        if (a ==null || b == null)
            return -1;

        int resLen = 0;
        if(a.length() == b.length())
        {
            resLen = sameLenStringDistance(a,b);
        }
        else if (a.length() > b.length())
        {
            for(int i=0;i<=a.length()-b.length();i++)
            {
                String newStr = a.substring(i,i+b.length());
                resLen += sameLenStringDistance(newStr,b);
            }
        }
        else if (b.length() > a.length())
        {
            for(int i=0;i<=b.length()-a.length();i++)
            {
                String newStr = b.substring(i,i+a.length());
                resLen += sameLenStringDistance(newStr,a);
            }
        }

        return resLen;
    }

    public  static  int sameLenStringDistance(String a ,String b)
    {
        int resLen = 0;

        for(int i=0 ; i< a.length();i++)
        {
            if (a.charAt(i) != b.charAt(i))
                resLen++;
        }

        return resLen;
    }

}