题解：CF873F Forbidden Indices

· · 题解

把P3804【模板】后缀自动机（SAM）的代码改改就过了。
区别 1：子串出现次数可以等于 1。
区别 2：对于所有能够计算贡献的结尾对应的字符串，cnt[cur] 要赋值为 1，否则为 0。 

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mpi make_pair
#define fi first
#define se second
#define lb(x) (x&-x)
using namespace std;
const int maxn=4e5+10;
const int maxm=1e5+10;
const int INF=1e18;
const int eps=1e-4;
string s,f;
int len,ans;
vector <int> g[maxn];
namespace SAM
{
    struct state{int len,link,nxt[30];}st[maxn];
    int siz,lst,cnt[maxn];
    void init(){st[0].len=0,st[0].link=-1,lst=siz=0;}
    void insert(char ch,int k)
    {
        int cur=++siz,num=ch-'a'+1;
        cnt[cur]=k;//区别2
        st[cur].len=st[lst].len+1;
        int p=lst;
        while (p!=-1&&!st[p].nxt[num]) st[p].nxt[num]=cur,p=st[p].link;
        if (p==-1) st[cur].link=0;
        else
        {
            int q=st[p].nxt[num];
            if (st[q].len==st[p].len+1) st[cur].link=q;
            else
            {
                int clone=++siz;
                st[clone]=st[q];
                st[clone].len=st[p].len+1;
                while (p!=-1&&st[p].nxt[num]==q) st[p].nxt[num]=clone,p=st[p].link;
                st[q].link=st[cur].link=clone;
            }
        }
        lst=cur;
    }
    void dfs(int x)
    {
        for (auto y:g[x]) dfs(y),cnt[x]+=cnt[y];
        if (x) ans=max(ans,cnt[x]*st[x].len);//区别1
        //P3804 【模板】后缀自动机（SAM）上的代码：
        //if (x&&cnt[x]>1) ans=max(ans,cnt[x]*st[x].len);
    }
}
using namespace SAM;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin >> len >> s >> f;
    for (int i=0;i<len;i++) insert(s[i],(f[i]=='0'));
    for (int i=1;i<=siz;i++) g[st[i].link].push_back(i);
    dfs(0);
    cout << ans;
    return 0;
}