string

发布时间：2020-12-15 05:34:15 所属栏目：Java 来源：网络整理

导读：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 c

string

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

题目描述

We call?

There is a string?

输入描述:

A line containing a string?

输出描述:

A positive?integer - the largest possible number of substrings of

输入

abac

输出

说明

The set of following substrings is such a choice:?

备注:

? 不等价大约是让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],num[N],len[N],c[N],last,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("%lldn",(ans+PT.L-2-(l+1)*(l+1))/2);//
    return 0;
}

回文树+后缀数组

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!