2019牛客多校-Day4

Posted on | Edited on | In | Views:

I. String

题意

定义两个字符串不等为 $a\ne b \&\& a\ne rev(b) $

给一个字符串，问由它的子串构成的 任意两个元素都不等 的最大集合有多大

题解

显然答案为 $a,rev(a)$ 中本质不同的子串的数量除 2，注意若子串为回文串则只被计了一次，所以还需要加上一个 $a$ 中本质不同回文串的数量再除 2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
int t1[N],t2[N],c[N],srank[N],height[N],sa[N];
bool cmp(int *r,int a,int b,int l){
    return r[a] == r[b] && r[a+l] == r[b+l];
}
void DA(int str[],int n,int m){//m为字符串中的最大值+1
    n++;
    int i, j, p, *x = t1, *y = t2;
    //第一轮基数排序，如果s 的最大值很大，可改为快速排序
    for(i = 0;i < m;i++)c[i] = 0;
    for(i = 0;i < n;i++)c[x[i] = str[i]]++;
    for(i = 1;i < m;i++)c[i] += c[i-1];
    for(i = n-1;i >= 0;i--)sa[--c[x[i]]] = i;
    for(j = 1;j <= n; j <<= 1){
        p = 0;
        //直接利用sa 数组排序第二关键字
        for(i = n-j; i < n; i++)y[p++] = i;//后面的j 个数第二关键字为空的最小
        for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;//这样数组y保存的就是按照第二关键字排序的结果
        //基数排序第一关键字
        for(i = 0; i < m; i++)c[i] = 0;
        for(i = 0; i < n; i++)c[x[y[i]]]++;
        for(i = 1; i < m;i++)c[i] += c[i-1];
        for(i = n-1; i >= 0;i--)sa[--c[x[y[i]]]] = y[i];//根据sa 和x 数组计算新的x 数组
        swap(x,y);
        p = 1; x[sa[0]] = 0;
        for(i = 1;i < n;i++)x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        if(p >= n)break;
        m = p;//下次基数排序的最大值
    }
    int k = 0;
    n--;
    for(i = 0;i <= n;i++)srank[sa[i]] = i;
    for(i = 0;i < n;i++){
        if(k)k--;
        j = sa[srank[i]-1];
        while(str[i+k] == str[j+k])k++;
        height[srank[i]] = k;
    }
}
const int C = 26;
struct Palindromic_Tree {
    int next[N][C] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
    int fail[N] ;//fail指针，失配后跳转到fail指针指向的节点
    int cnt[N] ;//cnt[i]表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
    int num[N] ;//num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
    int len[N] ;//len[i]表示节点i表示的回文串的长度
    int S[N] ;//存放添加的字符
    int last ;//指向上一个字符所在的节点，方便下一次add
    int n ;//字符数组指针
    int p ;//节点指针

    int newnode ( int l ) {//新建节点
        for ( int i = 0 ; i < C ; ++ i ) next[p][i] = 0 ;
        cnt[p] = 0 ;
        num[p] = 0 ;
        len[p] = l ;
        return p ++ ;
    }

    void init () {//初始化
        p = 0 ;
        newnode (  0 ) ;
        newnode ( -1 ) ;
        last = 0 ;
        n = 0 ;
        S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
        fail[0] = 1 ;
    }

    int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
        while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
        return x ;
    }

    void add ( int c ) {
        c -= 'a' ;
        S[++ n] = c ;
        int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
        if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
            int now = newnode ( len[cur] + 2 ) ;//新建节点
            fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
            next[cur][c] = now ;
            num[now] = num[fail[now]] + 1 ;
        }
        last = next[cur][c] ;
        cnt[last] ++ ;
    }

    void count () {
        for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
        //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
    }
} PAM;
int r[N];
char s[N];
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    in(s);
    ll n=strlen(s);
    s[n]='`';
    PAM.init();
    for0(i,n) {
        s[2*n-i]=s[i];
        PAM.add(s[i]);
    }
    ll m=2*n+1;
    for0(i,m)r[i]=s[i]-'`'+1;
    r[m]=0;
    DA(r,m,30);
    ll ans=PAM.p-2+m*(m+1)/2-(n+1)*(n+1);
    for(int i=2;i<=m;i++)ans-=height[i];
    outln(ans/2);
    return 0;
}