PROBLEM LINK:
Author: Rushil Patel
Tester: Anupam Singh
Editorialist: Rushil Patel
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Tree, Rolling Hash, Tries
PROBLEM:
You have to process the queries and either make new string from another previously made string or answer length of the longest common prefix of two strings.
QUICK EXPLANATION:
You can model the process of appending the characters to previously made string as a problem of trees / tries. Here, if we consider the tree solution then length of the longest common prefix of two strings can be found using binary lifting and rolling hashes.
EXPLANATION:
Let’s first observe that if we add a vertex with some id and character when we are asked to make a new string, then the new string is just the path from root to that vertex (root is for the empty string). We want to find the longest common prefix of two strings. If you observe then length of longest common prefix is depth(LCA) + C, where C is some non negative integral value. So now the main thing is how to deal with the extra C because we know a standard method to find LCA. Can we somehow use the method to find LCA in a tree? Yes we can. We just have to make some changes. If you use rolling hashes and store the hash value of the path from the root to all the vertices, then you can compare two paths starting from the root in O(1). So now you can use binary lifting in the same manner we use it to find LCA of any two vertices in a tree. But instead of comparing depth we compare hash values (Refer to the solution for better understanding) and find the longest depth upto which the prefix is common / same.
TIME COMPLEXITY:
O ((N+Q) * logN) for each Test Case.
SOLUTION:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define dracarys ios_base::sync_with_stdio(0);cin.tie(0);
#pragma GCC optimize("Ofast")
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod0 = 1e9 + 7, mod1 = 1e9 + 9;
const int mxQ = 2e5 + 5 , mxN = 2e5 + 5;
int n , q;
const int LOGN = 23;
int dp[LOGN][mxN] , LOG[mxN] , depth[mxN];
vector<int> g[mxN];
const int base = 27;
ll prefix[2][mxN] , pwr[2][mxN];
char s[mxN];
void pre(){
for (int i = 1;i < LOGN;i++){
for (int v = 1;v <= n;v++){
dp[i][v] = dp[i - 1][dp[i - 1][v]];
}
}
}
int jump(int x , int L){
for (int i = 0;i <= LOG[L];i++){
if (L & (1 << i)){
x = dp[i][x];
}
}
return x;
}
void dfs(int cur,int p,int lvl){
dp[0][cur] = p;
depth[cur] = lvl;
if (cur){
prefix[0][cur] = ((ll)(s[cur] - 'a' + 1) * pwr[0][lvl]) % mod0 + prefix[0][p];
prefix[1][cur] = ((ll)(s[cur] - 'a' + 1) * pwr[1][lvl]) % mod1 + prefix[1][p];
}
prefix[0][cur] = (prefix[0][cur] >= mod0 ? prefix[0][cur] - mod0 : prefix[0][cur]);
prefix[1][cur] = (prefix[1][cur] >= mod1 ? prefix[1][cur] - mod1 : prefix[1][cur]);
for (int& x : g[cur]){
if (x == p) continue;
dfs(x , cur , lvl + 1);
}
}
int ROOT = 0;
int mod_lca(int x,int y){
if (depth[x] < depth[y])
swap(x , y);
x = jump(x , depth[x] - depth[y]);
if (prefix[0][x] == prefix[0][y] && prefix[1][x] == prefix[1][y])
return depth[x];
for (int i = LOG[depth[x]];i >= 0;i--){
if (prefix[0][dp[i][x]] == prefix[0][dp[i][y]] && prefix[1][dp[i][x]] == prefix[1][dp[i][y]]) continue;
x = dp[i][x];y = dp[i][y];
}
return depth[dp[0][x]];
}
void reset(){
for (int i = 0;i <= n;i++){
g[i].clear();
}
}
void solve(int tt){
cin >> q;
vector<array<int,2>> Q;
n = 0;
char ch;
for (int type , str1 ,str2; q ; q--){
cin >> type;
if (type == 1){
++n;
cin >> str1 >> ch;
g[str1].push_back(n);
g[n].push_back(str1);
s[n] = ch;
}
else{
cin >> str1 >> str2;
Q.push_back({str1 , str2});
}
}
dfs(0 , 0 , 0);
pre();
for (auto& xx : Q){
cout << mod_lca(xx[0] , xx[1]) << "\n";
}
reset();
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int tt = 0,t = 1;
cin >> t;
pwr[0][0] = pwr[1][0] = 1;LOG[0] = -1;
for (int i = 1;i < mxQ;i++){
pwr[0][i] = (pwr[0][i - 1] * base) % mod0;
pwr[1][i] = (pwr[1][i - 1] * base) % mod1;
for (int j = LOGN;~j;j--){
if (i & (1 << j)){
LOG[i] = j;
break;
}
}
}
while(t--){solve(++tt);}
cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s ";
return 0;
}
Tester’s Solution
#include<bits/stdc++.h>
using ll = long long int;
using namespace std;
#define sync ios_base::sync_with_stdio(false); cin.tie(NULL)
using ld = long double;
#define input(arr,n) for(ll i1=0;i1<n;i1++ )cin>>arr[i1]
#define mod 1000000007
#define F first
#define S second
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
//recursions
#pragma comment(linker, "/stack:200000000")
//loops
#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>//s.order_of_key(val) *s.find_by_order(ind)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<string> split(const string& s, char c) {
vector<string> v; stringstream ss(s); string x;
while (getline(ss, x, c)) v.push_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
stringstream s; s << "[";
for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
s << arr[n - 1] << "]";
return s.str();
}
#define EVARS(args...) {__evars_begin(__LINE__); __evars(split(#args, ',').begin(), args);}
inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
template<typename T> inline void __evars_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
template<typename T> inline void __evars_out_var(T* val) { cerr << arrStr(val, 10); }
template<typename T> inline void __evars_out_var(T val) { cerr << val; }
inline void __evars(vector<string>::iterator it) { cerr << endl; }
template<typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
__evars_out_var(a);
cerr << "; ";
__evars(++it, args...);
}
const int N = 1e6 + 5;
struct Trie{
Trie *child[26] = {NULL};
int id = 0;
char val;
};
int main()
{
sync;
clock_t clk = clock();
int t;
cin >> t;
while(t--){
int q;
cin >> q;
Trie *root = new Trie;//initialization
vector<Trie*> address;
address.push_back(root);
vector<int> lev;
lev.push_back(0);//root
vector<vector<int> > sp;//sparse table
vector<int> aux_0(21);
sp.push_back(aux_0);//root
while(q--){
int type;
cin >> type;
if(type == 1){
int str;
char ch;
cin >> str >> ch;
Trie *curr = address[str];
vector<int> aux;
str = curr->id;
aux.push_back(str);
lev.push_back(lev[str] + 1);
if(!curr->child[ch - 'a']){
curr->child[ch - 'a'] = new Trie;
curr->child[ch - 'a']->id = address.size();
curr->child[ch - 'a']->val = ch;
}
curr = curr->child[ch - 'a'];
address.push_back(curr);
for(int i = 1; i <= 20; i++){
aux.push_back(sp[str][i - 1]);
str = sp[str][i - 1];
}
sp.push_back(aux);
//EVARS(aux.size());
}
else{
int str1, str2;
cin >> str1 >> str2;
if(lev[str1] < lev[str2])
swap(str1, str2);
for(int i = 20; i >= 0; i--){//bring to the same level
if(lev[str1] - (1 << i) >= lev[str2]){
str1 = sp[str1][i];
}
}
if(address[str1] != address[str2]){//they are not the same node
for(int i = 20; i >= 0; i--){
if(sp[str1][i] != sp[str2][i]){
str1 = sp[str1][i];
str2 = sp[str2][i];
}
}
str1 = sp[str1][0];
}
//EVARS(str1, str2);
cout << lev[str1] << '\n';
}
}
}
return 0;
}