链接：https://ac.nowcoder.com/acm/contest/884/I
来源：牛客网
题目描述
We call a,ba,ba,b non-equivalent if and only if a≠ba \neq ba=b and a≠rev(b)a \neq rev(b)a=rev(b), where rev(s)rev(s)rev(s) refers to the string obtained by reversing characters of sss, for example rev(abca)=acbarev(abca)=acbarev(abca)=acba.
There is a string sss consisted of lower-case letters. You need to find some substrings of sss 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.
示例1
输入
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∣≤2×1051 \leq |s|\leq 2 \times 10^51≤∣s∣≤2×105, sss is consisted of lower-case letters.
题解:
题目给你一个字符串s,让你求s中的子串组成的最大集合，满足这个集合内的每一个子串str, str和rev(str)不同时存在{rev(str):表示str反过来}
思路：就是先用SAM统计出s#rev(s)中不包含 '#'的所有子串ans1; 然后用PAM统计出s中本质不同的子串数量ans2;
这答案就是(ans1+ans2)/2;
为什么呢？
因为在用SAM统计s#rev(s)的时候会把所有字符串统计两边，而本身就是回文串的只会统计一遍。
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pil pair<int,long long>
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3fll;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int maxn=4e5+;
const int MAXN=4e5+;
char str[maxn];
int s[maxn];
ll ans;
struct SAM{
int l[maxn<<],fa[maxn<<],nxt[maxn<<][];
int last,cnt; void Init()
{
ans=;last=cnt=;
l[cnt]=fa[cnt]=;
memset(nxt[cnt],,sizeof(nxt[cnt]));
} int NewNode()
{
++cnt;
memset(nxt[cnt],,sizeof(nxt[cnt]));
l[cnt]=fa[cnt]=;
return cnt;
} void Insert(int ch)
{
int np=NewNode(),p=last;
last=np; l[np]=l[p]+;
while(p&&!nxt[p][ch]) nxt[p][ch]=np,p=fa[p];
if(!p) fa[np]=;
else
{
int q=nxt[p][ch];
if(l[p]+==l[q]) fa[np]=q;
else
{
int nq=NewNode();
memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
fa[nq]=fa[q];
l[nq]=l[p]+;
fa[np]=fa[q]=nq;
while(nxt[p][ch]==q) nxt[p][ch]=nq,p=fa[p];
}
}
ans+=1ll*(l[last]-l[fa[last]]);
} }sam; struct Palindromic_Tree{
int next[MAXN][];
int fail[MAXN];
int cnt[MAXN];
int num[MAXN];
int len[MAXN];
int S[MAXN];
int last;
int n;
int p; int newnode(int l)
{
for(int i=;i<;++i) next[p][i]=;
cnt[p]=;
num[p]=;
len[p]=l;
return p++;
} void Init()
{
p=;
newnode( );
newnode(-);
last=;
n=;
S[n]=-;
fail[]=;
} int get_fail(int x)
{
while(S[n-len[x]-]!=S[n])x=fail[x] ;
return x ;
} void add(int c)
{
S[++ n]=c;
int cur=get_fail(last) ;
if(!next[cur][c])
{
int now=newnode(len[cur]+) ;
fail[now]=next[get_fail(fail[cur])][c] ;
next[cur][c]=now ;
num[now]=num[fail[now]]+;
}
last=next[cur][c];
cnt[last]++;
} ll count()
{
ll res=p*1ll;
for(int i=p-;i>=;--i) cnt[fail[i]]+=cnt[i];
//for(int i=1;i<=p;++i) res+=cnt[i];
//cout<<"res "<<res<<endl;
return (res-);
}
} pam; int main()
{
scanf("%s",str);
int len=strlen(str); sam.Init();
for(int i=;i<len;++i) sam.Insert(str[i]-'a');
sam.Insert();
for(int i=len-;i>=;--i) sam.Insert(str[i]-'a');
ans-=1ll*(len+)*(len+);
//cout<<"ans "<<ans<<endl;
pam.Init();
for(int i=;i<len;++i) pam.add(str[i]-'a');
ans=ans+pam.count(); printf("%lld\n",(ans/2ll)); return ;
}