P1425子串清除Accepted
标签：[显示标签]
描述
我们定义字符串A是字符串B的子串当且仅当我们能在B串中找到A串。现在给你一个字符串A，和另外一个字符串B，要你每次从B串中从左至右找第一个A串，并从B串中删除它，直到A串不为B串的子串，问你需要进行几次删除操作。
格式
输入格式
输入文件共2行，第一行一个字符串A（长度小于256），第二行一个字符串B。
30%的数据是随机生成的；
50%的数据满足输入文件大小小于300KB；
100%的数据满足输入文件小于500KB，字符串A、B中只会出现英文字母。
输出格式
输出文件只有一个整数N。
样例1
样例输入1[复制]
abc
abcabcabaabcbccc
样例输出1[复制]
5
限制
1 second
提示
样例说明:abcabcabaabcbccc-> abcabaabcbccc-> abaabcbccc-> ababccc-> abcc
来源
Conan From HNSDFZ
【题解】
KMP问题。
找到一个匹配之后很正常的想法就是把那个匹配删掉。然后指针往前移动2*模式串的长度(这样就可以避免后面的串往前移动漏解了);
然后j=0继续找匹配；
但是直接把它删掉会超时(s.erase()这个函数);
所以考虑边读边输入。
直接指针往前移动模式串的长度，然后把新读入的东西覆盖在删掉的串的开头即可。
当然。不用真的边读边输入。先整串输入下来存成temp，然后再模拟输入就好了。
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
string s2, s1,temp;
int f[200000];
int main()
{
cin >> s2;
int len2 = s2.size();
f[0] = 0; f[1] = 0;
for (int i = 1; i <= len2 - 2; i++)//获取失配函数
{
int t = f[i];
while (t && s2[i] != s2[t]) t = f[t];
f[i + 1] = s2[i] == s2[t] ? t + 1 : 0;
}
int i = 0, j = 0, num = 0,top =0,now = 0;
cin >> temp;//先整串读入下来
int mt = temp.size();
s1 = temp;//用一个top指向当前已经读到哪里了。
while (true)
{
if (i == top)//如果扫描到了需要读入的地方
{
s1[i] = temp[now++];//就模拟读入
top++;//这里可能覆盖了原来删掉的东西。
}
while (j && s2[j] != s1[i]) j = f[j];
if (s2[j] == s1[i]) j++;//KMP算法
if (j == len2)
{
num++;
j = 0;
i = i-len2*2;//这样就可以避免影响了
top -= len2;//串的长度会减少len2
if (i < 0)
i = 0;
}
else
i++;
if (now == mt)//如果已经读到最后一位了。则结束。
break;//如果是在最后一位匹配，那么之前也都不会受到影响了。所以可以大胆的结束
}
printf("%d\n", num);
return 0;
}2
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int MAXN = 20e4;
string a,b;
int lena,lenb,f[MAXN],i = 1,top = 1,j = 1,now = 1,ans = 0;
string s;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
cin >> a;
cin >> b;
a=' '+a;
b=' '+b;
lena = a.size()-1;
lenb = b.size()-1;
f[1] = f[2] = 1;
for (int i = 2;i <= lena-1;i++)
{
int t = f[i];
while (t > 1 && a[i]!=a[t]) t = f[t];
f[i+1] = a[i]==a[t]?t+1:1;//a[i]和a[t]相同,那么当a[i+1]失配了
//可以从i+1跳到t+1;看看a[t+1]是不是和所需要的字母相同;
//跳跃!
}
s = b;//一开始s是一个空的字符串;得随便给他赋值一个东西;
while (true)
{
if (top==i)
{
s[i] = b[now++];
top++;
}
while (j>1 && s[i]!=a[j]) j = f[j];
if (s[i]==a[j])
j++;
if (j>lena)
{
i-=lena*2;
if (i<1)
i = 1;
top -=lena;
j = 1;
ans++;
}
else
i++;
if (now>lenb)
break;
}
cout << ans << endl;
return 0;
}