Input Description:

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

Output description:

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.

Remarks:

1≤∣s∣≤2×1051 \leq |s|\leq 2 \times 10^51≤∣s∣≤2×105, sss is consisted of lower-case letters.

Solutions:

The title gives you a string s, so that you can find the maximum set of substrings in s, which satisfies that every substring str, STR and rev(str) in this set exists at different times {rev(str): denotes str conversely}

The idea is to use SAM to count all the substrings ans1 that do not contain' Rev (s), and then use PAM to count the number of substrings ans2 that are essentially different in S.

The answer is (ans1+ans2)/2.

Why?

Because when using SAM to count s Rev (s), all strings will be counted on both sides, while palindrome strings themselves will only be counted once.

Reference code:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define pii pair<int,int>
  5 #define pil pair<int,long long>
  6 const int INF=0x3f3f3f3f;
  7 const ll inf=0x3f3f3f3f3f3f3f3fll;
  8 inline int read()
  9 {
 10     int x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    
 13     return x*f;
 14 }
 15 const int maxn=4e5+10;
 16 const int MAXN=4e5+10; 
 17 char str[maxn];
 18 int s[maxn];
 19 ll ans;
 20 struct SAM{
 21     int l[maxn<<1],fa[maxn<<1],nxt[maxn<<1][30];
 22     int last,cnt;
 23     
 24     void Init()
 25     {
 26         ans=0;last=cnt=1;
 27         l[cnt]=fa[cnt]=0;
 28         memset(nxt[cnt],0,sizeof(nxt[cnt]));        
 29     }
 30     
 31     int NewNode()
 32     {
 33         ++cnt;
 34         memset(nxt[cnt],0,sizeof(nxt[cnt]));
 35         l[cnt]=fa[cnt]=0;
 36         return cnt;    
 37     }
 38     
 39     void Insert(int ch)
 40     {
 41         int np=NewNode(),p=last;
 42         last=np; l[np]=l[p]+1;
 43         while(p&&!nxt[p][ch]) nxt[p][ch]=np,p=fa[p];
 44         if(!p) fa[np]=1;
 45         else
 46         {
 47             int q=nxt[p][ch];
 48             if(l[p]+1==l[q]) fa[np]=q;
 49             else
 50             {
 51                 int nq=NewNode();
 52                 memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
 53                 fa[nq]=fa[q];
 54                 l[nq]=l[p]+1;
 55                 fa[np]=fa[q]=nq;
 56                 while(nxt[p][ch]==q) nxt[p][ch]=nq,p=fa[p];
 57             }    
 58         }    
 59         ans+=1ll*(l[last]-l[fa[last]]);    
 60     }
 61     
 62 }sam;
 63 
 64 struct Palindromic_Tree{
 65     int next[MAXN][26];
 66     int fail[MAXN];
 67     int cnt[MAXN];
 68     int num[MAXN];
 69     int len[MAXN];
 70     int S[MAXN];
 71     int last;
 72     int n;
 73     int p;
 74  
 75     int newnode(int l) 
 76     {
 77         for(int i=0;i<26;++i) next[p][i]=0;
 78         cnt[p]=0;
 79         num[p]=0;
 80         len[p]=l;
 81         return p++;
 82     }
 83  
 84     void Init() 
 85     {
 86         p=0;
 87         newnode( 0);
 88         newnode(-1);
 89         last=0;
 90         n=0;
 91         S[n]=-1;
 92         fail[0]=1;
 93     }
 94  
 95     int get_fail(int x)
 96     {
 97         while(S[n-len[x]-1]!=S[n])x=fail[x] ;
 98         return x ;
 99     }
100  
101     void add(int c) 
102     {
103         S[++ n]=c;
104         int cur=get_fail(last) ;
105         if(!next[cur][c]) 
106         {
107             int now=newnode(len[cur]+2) ;
108             fail[now]=next[get_fail(fail[cur])][c] ;
109             next[cur][c]=now ;
110             num[now]=num[fail[now]]+1;
111         }
112         last=next[cur][c];
113         cnt[last]++;
114     }
115  
116     ll count() 
117     {
118         ll res=p*1ll;
119         for(int i=p-1;i>=0;--i) cnt[fail[i]]+=cnt[i];
120         //for(int i=1;i<=p;++i) res+=cnt[i];
121         //cout<<"res "<<res<<endl;
122         return (res-2);
123     }
124 } pam;
125 
126 int main()
127 {
128     scanf("%s",str);
129     int len=strlen(str);
130     
131     sam.Init();
132     for(int i=0;i<len;++i) sam.Insert(str[i]-'a');
133     sam.Insert(28);
134     for(int i=len-1;i>=0;--i) sam.Insert(str[i]-'a');
135     ans-=1ll*(len+1)*(len+1);
136     //cout<<"ans "<<ans<<endl;
137     pam.Init();
138     for(int i=0;i<len;++i) pam.add(str[i]-'a');
139     ans=ans+pam.count();
140     
141     printf("%lld\n",(ans/2ll));
142     
143     
144     return 0;    
145 }