E. Cool Slogans

题意：

　　给定一个字符串S，从中选出k个子串a[1],a[2]...a[k]，满足a[i]在a[i+1]中出现了两次（可以重叠），求最大的k。

分析：

　　建出SAM，在parent树上dp，dp[i]表示到第i个点，最多选了多少个子串，那么如果fa[i]在i中出现了两次，就可以+1后转移，否则直接继承fa[i]的值即可。

　　那么如何判断一个串是否在另一个串中出现了两次？

　　后缀自动机上每个点表示多个串，如果点A对应的串在点B对应的串中出现了两次，那么设B的结尾节点是$R_1, R_2...R_k$，那么从这些结尾位置任选一个，设为pos，满足$pos-len[B]+len[A] \sim pos$，A的right集合中，至少满足有两个right在这个区间中。

　　--------------------------------------------------------------------------------------------

　　这个dp这的好妙妙妙啊。

　　那么首先从dp的过程说起。这个dp感觉不太像dp，倒像是模拟。

　　我们从一个点A出发，设这个点的对应的最长的串是aba，然后向下走。这个点一定至少包含两个儿子结点。假设它有两个儿子节点，分别是x,y。

　　我们首先向x走，存在这一条边就说明了A的right集合和x的不同，且A包含x。然后我们判断x对应的子串是否有两个A，如果有，那让f[x]=f[A]+1即可。没有的话，我们记录下A这个位置（top），然后继续往下走，判断走到的每个点对应的子串是否有两个A，而不是有两个fa[i]。

　　因为A在这里分叉了，并且有x,y两个儿子，说明A（aba）在整个串中出现的位置至少有两次，前面的字符不同，假设是这样....caba.....daba.....那么往下走的过程是在当前的串上向前延伸的过程，一定会延伸到两个aba都包含了，然后转移。（这里x,y中只有一个会延伸到两个同时包含）。

　　还有一个疑问，就是为什么在计算A在B中是否出现了两次的时候，用的是A这个点，所对应的最长的串，是不是让这个串缩短一下，然后就出现两次了？那么我们考虑ba是否比aba优：如果A存在一个父节点是ba的话，那么我们肯定是用到了ba，如果不存在，说明ba和aba出现的Right集合是一样的，那么aba和ba是一样的。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int fa[N], ch[N][], len[N], xl[N], pos[N], tmp[N], f[N], top[N];

int ls[N * ], rs[N * ], Root[N];

int tot, Index = , Last = , n;

char s[N];

void update(int l,int r,int &rt,int p) {

    if (!rt) rt = ++tot;

    if (l == r) return ;

    int mid = (l + r) >> ;

    if (p <= mid) update(l, mid, ls[rt], p);

    else update(mid + , r, rs[rt], p);

}

int Merge(int x,int y) {

    if (!x || !y) return x + y;

    int z = ++tot; // ÕâÀï±ØÐëÒªÐÂ½¨Ò»¸öµã£¬ÒòÎªÒÔÇ°µÄµã»¹ÓÐÓÃ

    ls[z] = Merge(ls[x], ls[y]);

    rs[z] = Merge(rs[x], rs[y]);

    return z;

}

int query(int l,int r,int rt,int L,int R) {

    if (!rt) return ;

    if (L <= l && r <= R) return ;

    int mid = (l + r) >> ;

    if (L <= mid && query(l, mid, ls[rt], L, R)) return ;

    if (R > mid && query(mid + , r, rs[rt], L, R)) return ;

    return ;

}

void extend(int c,int i) {

    int NP = ++Index, P = Last; pos[NP] = i;

    len[NP] = len[P] + ;

    for (; P && !ch[P][c]; P = fa[P]) ch[P][c] = NP;

    if (!P) fa[NP] = ;

    else {

        int Q = ch[P][c];

        if (len[Q] == len[P] + ) fa[NP] = Q;

        else {

            int NQ = ++Index;

            len[NQ] = len[P] + ;

            pos[NQ] = pos[Q]; // !!!

            memcpy(ch[NQ], ch[Q], sizeof ch[Q]);

            fa[NQ] = fa[Q];

            fa[NP] = fa[Q] = NQ;

            for (; P && ch[P][c] == Q; P = fa[P]) ch[P][c] = NQ;

        }

    }

    Last = NP;

    update(, n, Root[NP], i);

}

int main() {

    freopen("a.in", "r", stdin);

    n = read();

    scanf("%s", s + );

    for (int i = ; i <= n; ++i) extend(s[i] - 'a', i);

    for (int i = ; i <= Index; ++i) tmp[len[i]] ++;

    for (int i = ; i <= n; ++i) tmp[i] += tmp[i - ];

    for (int i = Index; i >= ; --i) xl[tmp[len[i]]--] = i;

    for (int i = Index; i > ; --i) {

        int x = xl[i];

        Root[fa[x]] = Merge(Root[fa[x]], Root[x]);

    }

    int ans = ;

    for (int i = ; i <= Index; ++i) {

        int x = xl[i], y = fa[x];

        if (y == ) { f[x] = , top[x] = x; continue; }

        int z = query(, n, Root[top[y]], pos[x] - len[x] + len[top[y]], pos[x] - );

        if (z) f[x] = f[y] + , top[x] = x;

        else f[x] = f[y], top[x] = top[y];

        ans = max(ans, f[x]);

    }

    cout << ans;

    return ;

}

巴特西

CF 700 E. Cool Slogans

E. Cool Slogans

最新文章

热门文章