JZOJ 3337. 【NOI2013模拟】wyl8899的TLE【暴力】

233

• 題目：
• 題意：
• 分析：
• 代碼：

題目：

傳送門

題意：

給出兩個字元串，在 A A A串中至多修改一個字元，問這樣之後其在 B B B串比對子序列的最大長度是多少

分析：

我不想跟你多說話，并向你随手扔了個 n 2 n^2 n2暴力 . . . ... ...

然後就 A A A了，哈哈哈

想得美呢，雖然也差不多。好了，讓我們回到正題， n 2 n^2 n2的暴力可能肯定是過不去，那讓我們考慮下如何優化，我想到的是因為在逐字比對的時候如果遇上了連續相同的字元，我們完全可以省略這一段的比對，直接跳到第一個不相同的字元

設 g 1 g_1 g1​表示 A A A串每個相同的字元要加上多少位就能到達第一個不同的字元，如 A : a a a b b c A:aaabbc A:aaabbc，那麼 g 1 : 321211 g_1:321211 g1​:321211。 g 2 g_2 g2​表示 B B B串中的，在比對的過程中，一旦遇上了相同的，我們便可以跳到 m i n ( g 1 , g 2 ) min(g_1,g_2) min(g1​,g2​)

代碼：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long 
#define LZX IMS
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}   
char s1[50005],s2[50005];
int g1[50005],g2[50005];
int main()
{
	memset(g1,0x3f,sizeof(g1));memset(g2,0x3f,sizeof(g2));
	scanf("%s",s1+1);scanf("%s",s2+1);
	int l2=strlen(s2+1),l1=strlen(s1+1);
	g1[l1]=1;
	for(int i=l1-1;i;i--)
	  if(s1[i]==s1[i+1]) g1[i]=g1[i+1]+1;
	  else g1[i]=1;
	g2[l2]=1;
	for(int i=l2-1;i;i--)
	  if(s2[i]==s2[i+1]) g2[i]=g2[i+1]+1;
	  else g2[i]=1;
	int ans=0,tf,cnt,k,j;
	for(int i=1;i<=l2;i++)
	{
		if(ans==l1) break;
		tf=0;cnt=0;k=i;j=1;
		for(;j<=l1&&k<=l2;)
		{
			if(s1[j]==s2[k]) 
			{
				int giao=min(g1[j],g2[k]);
				j+=giao;k+=giao;
				cnt+=giao;
				continue;
			}
			if(s1[j]!=s2[k]&&tf) break; 
			if(s1[j]!=s2[k]&&!tf) tf=1,cnt++,j++,k++;
		}
		ans=max(ans,cnt);
	}
	cout<<ans;
	return 0;
}