Leetcode 214 Shortest Palindrome using KMP and Z Algorithms | String Matching Practice Problems

As we have covered Z and KMP Algorithms in the past videos, now we plan to solve some problems on these algorithms!

00:00-02:33 Introduction to Problem
02:34-04:21 Worst Case
04:22-08:07 Shifting of centre
08:08-11:55 Largest Palindromic Prefix idea
11:56-14:19 Brute Force O(N^2)
14:20-19:24 Using KMP for O(N)
19:25-21:14 Alternate using Z Algo
21:15-23:27 Code using KMP
23:28-26:09 Code using Z

[LogicKaMagic]

I Have done using Rolling Hash class Solution {
public:
const int MOD=1e9+7;
bool isPalindrome(int minimumRemoved, vector<int> &fHash, vector<int> &rHash, string &s, vector<int>&primePowers) {
int l1 = 0, r1 = s.size()-minimumRemoved-1;
int l2 = 0+minimumRemoved, r2 = s.size()-1;
int ffHash = getSubstrHash(l1, r1, fHash);
int rrHash = getSubstrHash(l2, r2, rHash);
int alignedffHash = (1LL * ffHash * primePowers[l2]) % MOD;
int alignedrrHash = (1LL * rrHash * primePowers[l1]) % MOD;
return true;
return false;
}
int getSubstrHash(int l, int r, vector<int> &hashes) {
if(l==0) return hashes[r];
return
}
string shortestPalindrome(string s) {
if(s.size()==0) return s;
string revS = s;
reverse(revS.begin(), revS.end());
vector<int> fHash(s.size());
vector<int> bHash(s.size());
vector<int> primePowers(s.size());
primePowers[0] =1;
fHash[0] = s[0]-'a'+1;
bHash[0]= revS[0]-'a'+1;
int p = 31;
for(int i=1 ;i<s.size();i++) {
primePowers[i] = (1LL*primePowers[i-1]*p)%MOD;
fHash[i] = (fHash[i-1] +
bHash[i] = (bHash[i-1] +
}
int minimumRemoved = s.size()-1;
for(int rem=0 ;rem<=s.size()-1;rem++) {
if(isPalindrome(rem, fHash, bHash, s, primePowers)) {
minimumRemoved = rem;
break;
}
}
string answer;
for(int answer+= s[i];
answer+= s;
return answer;
}
};

[junnunsafoan]

Bro literally the most diffcult part of this problem is understanding KMP and you don't even discuss it. Wasted my time unfortunately.

[dayashankarlakhotia]

Please make video on leetcode weekly contest qn.no.4