Codeforces 873F Forbidden Indices

什么屑题啊……

统计每个状态的 endpos 内不被禁止的位置的个数，乘该状态的 len，取最大值即可。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5;
int n;
char s[N + 5],t[N + 5];
long long ans;
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int sz[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    inline void insert(int x)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1,sz[p] = t[sam[p].len] ^ '1';
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
    {
        for(register int i = 1;i <= n;++i)
            insert(s[i] - 'a');
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= n;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sz[sam[a[i]].fa] += sz[a[i]];
    }
}
int main()
{
    scanf("%d%s%s",&n,s + 1,t + 1);
    SAM::build();
    for(register int i = 2;i <= SAM::tot;++i)
        ans = max(ans,(long long)SAM::sam[i].len * SAM::sz[i]);
    printf("%lld\n",ans);
}