MirzaMdAzwad

TamimHolmes

Aug 4th, 2021
592
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include<vector>
  3. #define fastio  ios_base::sync_with_stdio(0);cin.tie(NULL);
  4.  
  5. using namespace std;
  6. vector<int> prefix_function(string s) {
  7.     int n = (int)s.length();
  8.     vector<int> pi(n);
  9.     for (int i = 1; i < n; i++) {
  10.         int j = pi[i-1];
  11.         while (j > 0 && s[i] != s[j])
  12.             j = pi[j-1];
  13.         if (s[i] == s[j])
  14.             j++;
  15.         pi[i] = j;
  16.     }
  17.     return pi;
  18. }
  19.  
  20. int KMPSearch(string pat, string txt, int i){
  21.     int lenp=(int)pat.length();
  22.     int lent=(int)txt.length();
  23.     vector<int>lps=prefix_function(pat);
  24.  
  25.     int j=0;
  26.     int total=0;
  27.     while(i<lent){
  28.         if(pat[j]==txt[i]){
  29.             j++;
  30.             i++;
  31.         }
  32.  
  33.     if(j==lenp){
  34.         total++;
  35.         j=lps[j-1];
  36.     }
  37.     else if(i<lent && pat[j]!=txt[i]){
  38.         if(j!=0){
  39.             j=lps[j-1];
  40.         }
  41.         else i++;
  42.     }
  43. }
  44. return total;
  45. }
  46.  
  47. int main(){
  48.   int L,len,total,highest;
  49.   string x,tmp,temp;
  50.   while(cin>>L,cin>>x){
  51.     highest=-999;
  52.     len=x.length();
  53.     len=len-L;
  54.     for(int i=0;i<len;i++){
  55.       tmp=x.substr(i,L);
  56.       if(temp==tmp)continue;
  57.       total=KMPSearch(tmp,x,i);
  58.       if(total>highest){
  59.         highest=total;
  60.         temp=tmp;
  61.       }
  62.     }
  63.     cout<<temp<<'\n';
  64.   }
  65. }
  66.  
RAW Paste Data