nikunjsoni

686

Jun 26th, 2021
110
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 i=0, j=-1, n=pat.size();
  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.     int match(string txt, string pat){
  17.         int n=txt.size(), i=0, cnt=1, j=0, prevj=0;
  18.        
  19.         while(true){
  20.             while(j>=0 && txt[i] != pat[j])
  21.                 j = lps[j];
  22.             i++; j++;
  23.             if(j == pat.size()){
  24.                 return cnt;  
  25.             }
  26.             if(i == n){
  27.                 cnt++;
  28.                 i = 0;
  29.                 if(j <= prevj)
  30.                     return -1;
  31.                 prevj = j;
  32.             }
  33.         }
  34.         return cnt;
  35.     }
  36.  
  37.     int repeatedStringMatch(string a, string b) {
  38.         kmpPreprocess(b);
  39.         return match(a, b);
  40.     }
  41. };
RAW Paste Data