Advertisement
momo2345

Untitled

Jul 4th, 2022
1,236
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  4. #define ll long long
  5. #define tc int tc;cin>>tc;while(tc--)
  6. #define pb push_back
  7. #define endl "\n"
  8. #define spc " "
  9. #define yes "YES"
  10. #define no "NO"
  11. #define loop for(int i=0;i<n;i++) cin>>a[i]
  12. #define loop1 for(int i=0;i<n;i++) cin>>b[i]
  13. #define loop2 for(ll i=0;i<n;i++) cin>>c[i]
  14. #define beg begin()
  15. #define en end()
  16.  
  17. vector<int>prefix_function(string s){
  18. int m=s.size(),j;
  19. vector<int>pi(m,0);
  20. for(int i=1;i<m;i++){
  21.             j=pi[i-1];
  22. while(j>0 && (s[i]!=s[j])) j=pi[j-1];
  23. if(s[i]==s[j]){
  24.             j++; pi[i]=j;
  25. }
  26. }
  27. return pi;
  28. }
  29. int main()
  30. {
  31. suni;
  32. string s; cin>>s;
  33. vector<int>v=prefix_function(s);
  34. for(auto x : v) cout<<x<<" ";
  35. cout<<endl;
  36. }
  37.  
  38.  
Advertisement
RAW Paste Data Copied
Advertisement