hdu 3518 Boring counting (后缀自动机)

Posted by 111qqz on Saturday, November 11, 2017

TOC

http://acm.hdu.edu.cn/showproblem.php?pid=3518

题意:

给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路:

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

考虑其right集合,如果right集合中最大的r设为rightmost,最小的r设为leftmost.

那么如果rightmost-leftmost+1 > st[i].len ,说明什么呢?

说明该状态所表示的最长的字符串能够至少放下两个而不重叠。

即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。

如果最长的能放下,那么其他的也一定能放下。因此对答案贡献为st[i].len - st[st[i].link].len

如果rightmost-leftmost+1<=st[i].len,也就是rightmost-leftmost<st[i].len

这个时候长的字符串因为重叠了不能出现2次,但是短的字符串仍然可以贡献答案。

考虑如下图:

此时对答案的贡献为rightmost-leftmost+1 - (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len

综合2种情况,SAM中每个节点对答案的贡献是** min(rightmost-leftmost,st[i].len)-st[st[i].link].len**

需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案

leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。

/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :4436.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
#define MAXALP 30
const int mod = 2012;
struct state
{
    int len, link, nxt[MAXALP];
    int leftmost; //由于要求出现位置最小的,所以维护某个状态的right集合中r值最小的
    int rightmost;
};
const int N =1E3+7;
state st[N*2];
int sz, last,rt;
char s[N];
int cnt[2*N],rk[2*N];//for radix sort
void sa_init()
{
    sz = 0;
    last = rt = ++sz;
    st[1].len = 0;
    st[1].link=-1;
    st[1].rightmost=0;
    ms(st[1].nxt,-1);
}
void sa_extend(int c,int head)
{
    int cur = ++sz;
    st[cur].len = st[last].len + 1;
    st[cur].leftmost = st[cur].rightmost = head;
    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));

    int p;
    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
        st[p].nxt[c] = cur;
    if (p == -1) {
        st[cur].link = rt;
    } else {
        int q = st[p].nxt[c];
        if (st[p].len + 1 == st[q].len) {

            st[cur].link = q;
        } else {
            int clone = ++sz ;
            st[clone].len = st[p].len + 1;
            st[clone].link = st[q].link;
            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
            st[clone].leftmost = st[q].leftmost;
            st[clone].rightmost = st[q].rightmost;
            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
                st[p].nxt[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
void topo()
{
    ms(cnt,0); 
    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
}
char S[N];
int main()
{
#ifndef  ONLINE_JUDGE 
        freopen("./in.txt","r",stdin);
#endif

    while (~scanf("%s",S))
    {
        if (S[0]=='#') break;
        sa_init();
        for ( int i = 0,len = strlen(S) ; i < len ; i++)
        {
        sa_extend(S[i]-'a',i);
        }
        
        topo();
        for ( int i = sz ; i >=1 ; i--)
        {
        int v = rk[i];
        int fa = st[v].link;
        st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
//      printf("len:%d rightmost %d leftmost:%d\n",st[i].len,st[i].rightmost,st[i].leftmost);
        } 
        
        LL ans = 0 ;
        for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
            ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
        printf("%lld\n",ans);
    }



#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}







/* ***********************************************
Author :111qqz
Created Time :2017年11月15日 星期三 19时06分15秒
File Name :SAM.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
#define MAXALP 30
const int N=1E3+7;
struct SAM
{
    struct state
    {
    int len, link, nxt[MAXALP];
    int leftmost; //某个状态的right集合中r值最小的
    int rightmost;//某个状态的right集合的r的最大值
    int Right; //right集合大小
    };
    state st[N*2];
    char S[N];
    int sz, last,rt;
    char s[N];
    int cnt[2*N],rk[2*N];//for radix sort
    void init()
    {
    sz = 0;
    last = rt = ++sz;
    st[1].len = 0;
    st[1].link=-1;
    st[1].rightmost=0;
    ms(st[1].nxt,-1);
    }
    void extend(int c,int head)
    {
    int cur = ++sz;
    st[cur].len = st[last].len + 1;
    st[cur].leftmost = st[cur].rightmost = head;
    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
    int p;
    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
        st[p].nxt[c] = cur;
    if (p == -1) {
        st[cur].link = rt;
    } else {
        int q = st[p].nxt[c];
        if (st[p].len + 1 == st[q].len) {

        st[cur].link = q;
        } else {
        int clone = ++sz ;
        st[clone].len = st[p].len + 1;
        st[clone].link = st[q].link;
        memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
        st[clone].leftmost = st[q].leftmost;
        st[clone].rightmost = st[q].rightmost;
        for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
            st[p].nxt[c] = clone;
        st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
    }
    void topo()
    {
    ms(cnt,0); 
    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
    }
    void pre()  //跑拓扑序,预处理一些东西
    {
    for ( int i = sz ; i >= 2 ; i--)
    {
        int v = rk[i];
        int fa = st[v].link;
        if (fa==-1) continue;
        st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
        st[fa].Right += st[v].Right;
    }
    }
    void solve()
    {

    LL ans = 0 ;
    for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
        ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
    printf("%lld\n",ans);
    }
}A;
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
#endif

    while (~scanf("%s",A.S))
    {
    if (A.S[0]=='#') break;
    A.init();
    for ( int i = 0,len = strlen(A.S) ; i < len ; i++)
        {
        A.extend(A.S[i]-'a',i);
        }
        A.topo();
    A.pre();
    A.solve();
    }
 
 
 
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付