nikunjsoni

214

Jun 27th, 2021
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     vector<int> lps;
  4.     void kmpPreprocess(string pat){
  5.         int n=pat.size(), i=0, j=-1;
  6.         lps.resize(n+1, 0);
  7.         lps[0] = -1;
  8.         while(i<n){
  9.             while(j>=0 && pat[i] != pat[j])
  10.                 j = lps[j];
  11.             i++; j++;
  12.             lps[i] = j;
  13.         }
  14.     }
  15.    
  16.    
  17.     string shortestPalindrome(string s) {
  18.         if(s == "") return "";
  19.         string pat = s;
  20.         reverse(s.begin(), s.end());
  21.        
  22.         int n = s.size();
  23.         kmpPreprocess(pat+"#"+s);
  24.         int len = n-lps.back();
  25.         return s.substr(0, len)+pat;
  26.     }
  27. };
RAW Paste Data