codeforces 123D. String(后缀自动机)

Posted by 111qqz on Monday, November 13, 2017

TOC

题目链接:http://codeforces.com/problemset/problem/123/D

题意:

如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

思路:

这道题可以考虑用后缀数组做,麻烦一点:codeforces-123D-解题报告(SA)

直接SAM

right[v]就是SAM上状态表示的所有字符串出现的次数。

那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)

累加即可。

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

//#include <bits/stdc++.h>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#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 55 //还有大写字母orz
int k;
struct state
{
    int len, link, nxt[MAXALP];
};
const int N =1E5+7;
state st[N*2];
int sz, last,rt;
char s[N];
int Right[2*N];
int cnt[2*N],rk[2*N];//for radix sort
int dp[2*N],lazy[2*N];
void sa_init()
{
    sz = 0;
    last = rt = ++sz;
    st[1].len = 0;
    st[1].link=-1;
    ms(st[1].nxt,-1);
}
void sa_extend(int c)
{
    int cur = ++sz;
    st[cur].len = st[last].len + 1;
    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));
            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 ST[N];
int idx( char c)
{
    if (c>='a'&&c<='z') return c-'a';
    return c-'A'+26;
}
int main()
{
#ifndef  ONLINE_JUDGE 
        freopen("./in.txt","r",stdin);
#endif
    ms(Right,0);
    ms(lazy,0); //parent树上的lazy标记,最后子底向上更新
    scanf("%s",ST);
//  cout<<"ST:"<<ST<<endl;
    sa_init();
    for (int i = 0,len = strlen(ST);  i < len ; i++)
    {
        Right[sz+1] = 1;
        sa_extend(idx(ST[i]));
    }
    topo();
    for ( int i = sz ; i >=1 ; i--) if (st[rk[i]].link!=-1)Right[st[rk[i]].link]+=Right[rk[i]];
    
    LL ans = 0 ;
    for ( int i = sz ; i >= 1 ; i--)
    {
        int v = rk[i];
        ans = ans + 1LL*Right[v]*(Right[v]+1)/2*(st[v].len-st[st[v].link].len);
        printf("ans:%lld\n",ans);
    }
    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;
const int N=5E5+7;
struct SAM
{
    #define MAXALP 30
    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
    int idx(char c)
    {
    if (c>='a'&&c<='z') return c-'a';
    return c-'A'+26;
    }
    void init()
    {
    sz = 0;
    ms(st,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 build ()
    {
    init();
    for ( int i = 0,_len = strlen(S) ; i < _len ; i++)
    {
        st[sz+1].Right = 1;
        extend(idx(S[i]),i);
    }
    }
    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];
    //rk[1]是len最小的状态的标号
    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 = sz ; i >= 2 ; i--)
    {
        int v = rk[i];
        if (st[v].link==-1) continue;
        ans = ans + 1LL * st[v].Right*(st[v].Right+1)/2 * (st[v].len-st[st[v].link].len);
    }
    printf("%lld\n",ans);
    }
    int LCS(char *s)
    {
    int ans = 0,len = 0 ;
    int p = rt;
    for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
    {
        int ID = s[i]-'a';
        if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
        else
        {
        while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
        if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
        }
      //  printf("len:%d\n",len);
        ans = max(ans,len);
    }
    return ans;
    }
}A;
char B[N]; 
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
#endif
    scanf("%s",A.S);
    A.build();
    A.topo();
    A.pre();
    A.solve();

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

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

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