string

string

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

We call a,b non-equivalent if and only if a≠b and a≠rev(b), where rev(s) refers to the string obtained by reversing characters of s, for example rev(abca)=acba.

There is a string s consisted of lower-case letters. You need to find some substrings of s so that any two of them are non-equivalent. Find out what's the largest number of substrings you can choose.

输入描述:

A line containing a string sss of lower-case letters.

输出描述:

A positive integer - the largest possible number of substrings of sss that are non-equivalent.

输入

abac

输出

8

说明

The set of following substrings is such a choice: abac,b,a,ab,aba,bac,ac,cabac,b,a,ab,aba,bac,ac,cabac,b,a,ab,aba,bac,ac,c.

备注:

1≤∣s∣≤2e5, s is consisted of lower-case letters.
链接：https://ac.nowcoder.com/acm/contest/884/I
来源：牛客网

---

题意：选择最多的字串，使得选择的字串两两不“匹配”。
思路（来自题解）：

• 不等价大约是让a和rev(a)只算一次？
• 考虑rev(s)和s中的不同子串个数，那么这样s和rev(s)就会大约恰好被算两次！
• 其实并不是所有s都是这样，如果s本身是回文的，那么s=rev(s)。
• 求出rev(s)和s中的不同子串个数p：
• 可以直接使用广义后缀自动机
• 也可以对s$rev(s)建立后缀数组，求出不同的子串个数，减去包含$的串个数即可，这些串显然是两两不同的
• 求出s中的不同回文串个数q：
• 使用回文树即可，也可以使用manacher+后缀数组，但是较为繁琐
• 答案即为(p+q)/2。

#include<bits/stdc++.h>
const int N = 4e5+50;
using namespace std;

struct SuffixArray {
    int sa[N],rank[N],height[N],cnt[N],a1[N],a2[N],n,m,*x,*y;
    void sort() {
        for(int i=0;i<m;i++) cnt[i]=0;
        for(int i=0;i<n;i++) cnt[x[i]]++;
        for(int i=1;i<m;i++) cnt[i]+=cnt[i-1];
        for(int i=n-1;i>=0;i--) sa[--cnt[x[y[i]]]]=y[i];
    }
    void build(char *s,int c_size) {
        n=strlen(s);m=c_size;
        x=a1;y=a2;
        for(int i=0;i<n;i++) x[i]=s[i],y[i]=i;x[n]=y[n]=-1;
        sort();
        for(int k=1;k<=n;k<<=1) {
            int p=0;
            for(int i=n-k;i<n;i++) y[p++]=i;
            for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;
            sort();
            p=0;std::swap(x,y);
            x[sa[0]]=0;
            for(int i=1;i<n;i++) {
                if(y[sa[i]]!=y[sa[i-1]]||y[sa[i]+k]!=y[sa[i-1]+k]) p++;
                x[sa[i]]=p;
            }
            if(p+1>=n) break;
            m=p+1;
        }
        for(int i=0;i<n;i++) rank[sa[i]]=i;
        height[0]=0;int k=0;
        for(int i=0;i<n;i++) {
            if(k) k--;
            if(rank[i]==0) continue;
            int j=sa[rank[i]-1];
            while(i+k<n&&j+k<n&&s[i+k]==s[j+k]) k++;
            height[rank[i]]=k;
        }
    }
}SA;

struct Palindromic_Tree
{
    int nxt[N][26],f[N],cnt[N],num[N],len[N],c[N],last,n,L;

    inline int newnode(int x)
    {
        for(register int i=0; i<26; ++i)
            nxt[L][i]=0;
        cnt[L]=0;
        len[L]=x;
        return L++;
    }
    void init()
    {
        L=0;
        newnode(0);
        newnode(-1);
        last=0;
        n=0;
        c[n]=-1;
        f[0]=1;
    }
    inline int getf(int x)
    {
        while(c[n-len[x]-1]!=c[n])
            x=f[x];
        return x;
    }
    inline void add(int x)
    {
        x-='a';
        c[++n]=x;
        int cur=getf(last);
        if(!nxt[cur][x])
        {
            int now=newnode(len[cur]+2);

            f[now]=nxt[getf(f[cur])][x];
            nxt[cur][x]=now;
        }
        ++cnt[last=nxt[cur][x]];
    }
    void count()
    {
        for(register int i=L-1; i>=2; --i)
            cnt[f[i]]+=cnt[i];
    }

} PT;

int main()
{
    char s[N]= {0};
    scanf("%s",s);

    PT.init();
    long long len=strlen(s);

    long long l=len;
    s[len]='#';
    for(int i=0; i<len; i++)s[len+i+1]=s[len-1-i],PT.add(s[i]);

    SA.build(s,256);

    len=len*2+1;
    long long ans=len*(len+1)/2;

    for(int i=1;i<len;i++)
    {
        ans-=SA.height[i];
    }

    printf("%lld
",(ans+PT.L-2-(l+1)*(l+1))/2);//
    return 0;
}