精简压缩版题意：
给出一个字符串 T ，在里面找出形如 A*B*C 的字符串并求出需要删去的最少字符数
其中 A,B,C 是给出的字符串, * 是任意字符
对于 100\% 的数据， 1≤|T|, |A|, |B|, |C|≤50000；
所有单词长度不超过 5 ，出现次数不超过 500 ；数据保证答案总存在。
读完题，可以发现一些性质：
-
1、A和C只要从开头和结尾暴力找，因为是 A*B*C， A 前面不能有单词，同理， C 后面也不能有单词，如果 T 中 开头/结尾 相应位置不相同，就将 删除单词数++
-
2、通过所有 单词出现次数不超过 500，发现：一共有可能出现最多 500 处能作为 B 的开头的单词，
所以可以进行暴力的搜索，枚举开头 L ，从 L 处向后暴力搜索答案
-
3、将第一步的删除单词数++改为用总长 - 字符串长度
发现了以上性质，恭喜！这道紫题成功变为一道暴力搜索黄题！
PS:没读懂的话可以对照样例根据性质手模一下
具体实现将在代码中详细注释
#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int a,b,c,n,ans;
//ans对应答案,a,b,c,n在读入中有解释
string sn[maxn],sa[maxn],sb[maxn],sc[maxn];
//
void read(int &n,string sn[]){
//读入，将读入的内容存进一个个sn[i]/sa[i]/sb[i]/sc[i]中
// n/a/b/c分别是sn/sa/sb/sc的长度
char ch;
do ch=getchar();while(ch<=32);
for(n=1;;n++){
do sn[n]+=ch,ch=getchar(); while(ch>32);
while(ch<=32){
if(ch=='\n'||ch==EOF) break; ch=getchar();
}
if(ch=='\n'||ch==EOF) break;//如果读到换行(读完了) 就break;
}
}
int main(){
int i,j;
read(n,sn);
read(a,sa);
read(b,sb);
read(c,sc);
// ↑ 读入
//注意：这里的长度是从1开始计算的
for(i=j=1;j<=a;i++){
//从1开始搜，i代表sn中目前搜索到的下标
//j代表sa中搜索的进度
if(sn[i]==sa[j]) ++j;
//如果相同，就将j向后推进
}
ans+=i-1-a;
//i的时候已经搜完了 实际上是比sa的最后一位所处下标多1的 i-1表示sa最后一位在sn中的下标
//i-1后-a减去sa的长度，算出多出的(要删去的字符数)
int l=i;
//i已经在sa结尾+1处，l=i是b可行的左端点
for(i=n,j=c;j>=1;i--){
//C的位置从n开始搜,i表示sn中的位置
//j表示sc中搜索进度,从后往前
if(sn[i]==sc[j]) --j;
//与搜索A时相同
}
//
ans+=n-i-c;//n-i是总长度用掉的
//用去的长度-C实际长度=删除字母长度
int r=i,id,mn=1e9;
//洛谷原题中的第一篇题解没有赋值mn的初始值，所以是拿不到多少分的（
//加上后是能AC的
for(;l<=r;l++){
//搜索B 左端点l 右端点r
if(sn[l]==sb[1]){
//如果符合b开头位置就开始搜索
for(i=l,j=1;j<=b;i++){
//同A/C的搜索过程
if(sn[i]==sb[j]) j++;
}
//i位置已经超了 1
if(i-1<=r&&mn>i-l-b){//如果没有超出范围且比目前的更优
mn=i-l-b;
id=i;
//同A/C的赋值
}
}
}
ans+=mn;
//加上答案
printf("%d",ans);
//输出答案
return 0;
}
觉得写得好就给个赞或留个言吧~
