蓝桥杯2023年第十四届省赛真题-子串简写

解题思路:观察题目可以发现，我们发现第i个是c₂可以组成的子串数量[0,i-k]这个区间内c₁的数量，所有我们只需要找到每个c₂(假设下标为i)[0,i-k]这个区间内c1的数量就可以得到答案。但是观察数据规模发现使用暴力的方法不能AC该题。

优化:

使用前缀和思想，另开一个数组,保存当前c1前（包括自身）有多少个c1,这样只需要找到i-k(假设下标为i)后最近的c1就好了

参考代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long x[500005];
        char s[500005];
	int n;
	scanf("%d",&n);
	char c1,c2;
	scanf("%s",s);
	scanf(" %c",&c1);
	scanf(" %c",&c2);
	long long a=0;
	for(int i=0;s[i]!='\0';i++)
	{
		if(s[i]==c1)
		{
			a++;
			x[i]=a;
		}
	}
	long long ans=0;
	for(int i=0;s[i]!='\0';i++)
	{
		if(s[i]==c2)
		{
			for(int j=i-n+1;j>=0;j--)
			{
				if(s[j]==c1)
				{
					ans+=x[j];
					break;
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

该题数据不够完美若数据为

1

abbb...省略5 × 10⁵-5个b...b a b

复杂度还是来到了o(n²)

此代码还可以再优化

可以再开一个数组保存距离最近的c1的下标

时间复杂度为o(n)