自动搬运

查看原文

来自洛谷，原作者为

	syf2008 **

搬运于2025-08-24 21:33:09，当前版本为作者最后更新于2021-08-12 21:44:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道字符串模拟题,举个例子:

我们来画张图：

这里有 $3$ 个区间，但我们只能选择 $2$ 个，因为有区间重合。

不难发现，这题就是求出所有子串的区间，记录下来，然后求最大不相交区间数量。

上代码

#include <bits/stdc++.h>
using namespace std;
struct ss
{
    int l,r;
}f[100005];
string a,b;
int s,n,lena,lenb,tmp=-2e9,ans;
bool cmp(ss a,ss b){return a.r<b.r;}
int main()
{
    cin>>a;
    lena=a.size();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>b;
        lenb=b.size();
        for(int j=0;j<=lena-lenb;j++)
        if(a.substr(j,lenb)==b) //求出符合要求的子串区间
        {
            ++s;
            f[s].l=j;
            f[s].r=j+lenb-1;
        }
    }
    sort(f+1,f+s+1,cmp);
    for(int i=1;i<=s;i++) //求最大不相交区间数量
    if(tmp<f[i].l)
    {
        tmp=f[i].r;
        ans++;
    }
    cout<<ans<<endl;
}