nikunjsoni

1392

Jun 27th, 2021
88
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.     string longestPrefix(string s) {
  17.         kmpPreprocess(s);
  18.         return s.substr(0, lps.back());
  19.     }
  20. };
RAW Paste Data