Advertisement
jayati

Longest Prefix Suffix

Sep 25th, 2023
896
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. //{ Driver Code Starts
  2. //Initial template for C++
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7.  
  8. // } Driver Code Ends
  9.  
  10. //User function template for C++
  11.  
  12. class Solution{
  13.   public:      
  14.     int lps(string s) {
  15.         // Your code goes here
  16.         int n=s.length();
  17.         int i=0;
  18.         int j=1;
  19.         vector<int> ans(n,0);
  20.         while(j<n)
  21.         {
  22.             if(s[i]==s[j])
  23.             {
  24.                 ans[j]=i+1;
  25.                 i++;
  26.                 j++;
  27.             }
  28.             else
  29.             {
  30.                 if(i!=0)
  31.                 {
  32.                     i=ans[i-1];
  33.                 }
  34.                 else
  35.                 {
  36.                     j++;
  37.                 }
  38.             }
  39.         }
  40.         return ans.back();
  41.     }
  42. };
  43.  
  44. //{ Driver Code Starts.
  45.  
  46. int main()
  47. {
  48.    
  49.  
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(NULL);
  52.     cout.tie(NULL);
  53.    
  54.     int t;
  55.     cin >> t;
  56.     while(t--)
  57.     {
  58.         string str;
  59.         cin >> str;
  60.  
  61.         Solution ob;
  62.  
  63.         cout << ob.lps(str) << "\n";
  64.     }
  65.  
  66.     return 0;
  67. }
  68.  
  69. // } Driver Code Ends
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement