古代遗迹：字符王国

第一行输入一个 $N(N \leq 100)$
每组数据的包括两行：
第一行输入字符串 $\text{S}$ ，
第二行输入字符串 $\text{T}$ 。
保证所有字符串都只有小写英文字母，并且 $1≤|T|≤|S|≤2*10^5$
（注：|S| 表示的是字符S的长度）

C++14(g++5.4) 解法, 执行用时: 152ms, 内存消耗: 912K, 提交时间: 2020-06-20 17:06:24

#include<bits/stdc++.h>
using namespace std;
int N;
string s, t;
bool judge(int *s, int* t)
{
	int sum = 0;
	for(int i = 'a'; i <= 'z'; i++)
		sum += abs(s[i]-t[i]);
	return sum <= 2;
}
int main()
{
	for(cin >> N; N--; )
	{
		cin >> s >> t;
		int cnts[256] = {0}, cntt[256] = {0}, i, ans = 0, len = t.size();
		for(i = 0; t[i]; i++)
			cntt[t[i]]++, cnts[s[i]]++;
		ans += judge(cnts, cntt);
		for(; s[i]; i++)
		{
			cnts[s[i-len]]--;
			cnts[s[i]]++;
			ans += judge(cnts, cntt);
		}
		cout << ans << endl;
	}
	
}

C++11(clang++ 3.9) 解法, 执行用时: 27ms, 内存消耗: 732K, 提交时间: 2020-06-22 22:46:35

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

char R[200005],T[200005];
int main()
{
    int i,j,k,t,n,m;
    scanf("%d",&t);
    while(t--)
    {
    	scanf("%s%s",R,T),n=strlen(R),m=strlen(T);
    	int V[26]={0},ans=0;
    	for(i=0;i<m;i++)V[T[i]-'a']++,V[R[i]-'a']--;
    	for(k=j=0;j<26;j++)if(V[j])k+=abs(V[j]);
    	if(k<3)ans++;
    	for(i=m;i<n;i++)
		{
			V[R[i]-'a']--,V[R[i-m]-'a']++;
			for(k=j=0;j<26;j++)if(V[j])k+=abs(V[j]);
    	    if(k<3)ans++;
		}
		printf("%d\n",ans);
	}
}

详情