Cpp solution using z-function


#1

IT’S THE SAME QUESTION AS TO INSERT MIN. NUMBER OF CHARACTERS AT THE BEGINNING
TO MAKE THE STRING PALINDROMIC.
JUST REVERSE THE INITIAL STRING GIVEN IN THE FUNCTION.
#define ll long long int

// z-function for string matching
vector z_function(string s) {
int n = (int) s.length();
vector z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}

int Solution::solve(string s) {
ll n = s.length() ;
int ans=-1 ;
if(n<=1)
return 0 ;
reverse(s.begin(), s.end()) ;
string res = s ;
reverse(s.begin(), s.end()) ;
res.push_back(’*’) ;
res += s ;

vector<int> z = z_function(res) ;

for(ll i=n+1; i<=2*n; i++)
    if(z[i]+(i-n-1) == n)
        ans = max(ans, z[i]) ;
    
return n-ans ;

}