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;

}