题解 P2031 脑力达人之分割字串

syf2008 · 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;
}