PROBLEM LINK
Author: Prahalad Singh
Tester: …
Editorialist: Sanyam Aggarwal
DIFFICULTY
HARD
PREREQUISITES
Suffix Tree
Dynamic Programming
String Theory
PROBLEM
In the Seventh episode of the Third Season of Rick and Morty as Rick and Morty were preparing to go to Atlantis, they were interrupted by Rick and Morty’s pair from the Citadel of Ricks looking for donations to the Citadel Redevelopment fund. Our Rick and Morty refute the possibility of donation with hostility and the pair left (pointing out that our Rick was the one to say no).
Imagine a scenario where our Rick chose to give them one more opportunity to Rick from Citadel after all Rick from Citadel looked precisely like him. So our Rick asked them a problem based on pairs, which Rick and Morty from Citadel couldn’t tackle since they were busy collecting donations, you liked the idea of donations for a social cause and chose to help them to crack the problem.
They were given a string str, determine the total n number of ways to cut string str to substrings such that if there are n (n is always even) substrings S_i (1≤i≤n) such that str=S_1S_2S_3S_4……..S_(n−1)S_n, then S_i=S_n−i+1 S_i=S_n−i+1 for all i(1 ≤i≤ n). Since the answer can be huge, calculate its modulo 10^9+7.
EXPLANATION
Let n be the length of the string s. Consider the string nstr = str[0]str[n - 1]str[1]str[n - 2]str[2]str[n - 3]...str[n / 2 - 1]str[n / 2]. The problem can be reduced to finding the number of ways to partition string nstr into palindromic substrings of even length.
Proof: Let k be the total number of partitions. Let
S_i = S_{k-i+1} for S_1S_2S_3...S_n where m denotes length of p_i and x_j denotes j_{th} character of p_i. The part of string str corresponding to these two partitions is p_1p_mp_2p_{m - 1}...p_{m - 1}p_2p_mp_1 and this an even length palindrome. Similarly, the converse is also true.
Dynamic programming can be used to solve the problem. Let dp[i] be the number of ways to partition t[1…i] into even length palindromes. Then, dp[i]=sigma(dp[i-1]) where nstr[j + 1...i] is an even length palindrome. Of course for odd i, dp[i] = 0.
we can use an EER tree to implement the solution. Further, we can avoid the use of any suffix structure by following the algorithm described here https://arxiv.org/pdf/1403.2431.pdf .
To know more about suffix tree: Suffix Trees Tutorials & Notes | Data Structures | HackerEarth
SOLUTION
Setter’s Solution
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
using namespace std;
const int MAXN=1000005;
string s;
struct PalindromicTree {
int N,cur;
vector<map<int,int>> next;
vector<int> link,start,len,diff,slink;
PalindromicTree(): N(0),cur(0)
{
node();
len[0]=-1;
node();
}
int node(){
next.emplace_back();
link.emplace_back(0);
start.emplace_back(0);
len.emplace_back(0);
diff.emplace_back(0);
slink.emplace_back(0);
return N++;
}
void add_letter(int idx){
while(true){
if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]);
cur=link[cur];
}
if(next[cur].find(s[idx])!=next[cur].end()){ cur=next[cur][s[idx]];
return; }
node();
next[cur][s[idx]]=N-1;
len[N-1]=len[cur]+2;
start[N-1]=idx-len[N-1]+1;
if(len[N-1]==1){
link[N-1]=diff[N-1]=slink[N-1]=1;
cur=N-1;
return;
} while(true){ cur=link[cur]; if(idx-len[cur]-1>=0 && s[idx-len[cur]-1]==s[idx]); }
link[N-1]=next[cur][s[idx]];
diff[N-1]=len[N-1]-len[link[N-1]];
if(diff[N-1]==diff[link[N-1]])
slink[N-1]=slink[link[N-1]];
else
slink[N-1]=link[N-1];
cur=N-1; } };
ll dp[MAXN],sans[MAXN];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
PalindromicTree pt;
int i,cur;
string str;
cin>>str;
for(i=0;i<sz(str)/2;i++){
s.pb(str[i]);
s.pb(str[sz(str)-i-1]);
}
dp[0]=1;
for(i=1;i<=sz(s);i++){
pt.add_letter(i-1);
for(cur=pt.cur;cur>1;cur=pt.slink[cur])
{
sans[cur]=dp[i-pt.len[pt.slink[cur]]-pt.diff[cur]];
if(pt.diff[cur]==pt.diff[pt.link[cur]])
sans[cur]=(sans[cur]+sans[pt.link[cur]])%hell;
dp[i]=(dp[i]+sans[cur])%hell;
}
if(i&1)
dp[i]=0;
}
cout<<dp[sz(s)];
return 0;
}