Advertisement
Korotkodul

ЗОШ Префикс-функция ОК

Jan 11th, 2022
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. using namespace std;
  12. using ll = long long;
  13. using ld = long double;
  14. using db = double;
  15. void cv(vector <int> &v){
  16. for (auto x: v) cout<<x<<' ';
  17. cout<<"\n";
  18. }
  19.  
  20. void cvl(vector <ll> &v){
  21. for (auto x: v) cout<<x<<' ';
  22. cout<<"\n";
  23. }
  24.  
  25.  
  26. void cvv(vector <vector <int> > &v){
  27. for (auto x: v) cv(x);
  28. cout<<"\n";
  29. }
  30.  
  31. int main()
  32. {
  33. ios::sync_with_stdio(0);
  34. cin.tie(0);
  35. cout.tie(0);
  36. string S; cin>>S; int n = S.size();
  37. pii lr; int l,r;
  38. vector <int> P(n, 0);
  39. for (int i = 1; i <n;++i){
  40. int j = P[i-1];
  41. while (j > 0 && S[j] != S[i]){
  42. j = P[j-1];
  43. }
  44. if (S[i] == S[j]){
  45. ++j;
  46. }
  47. P[i] = j;
  48. }
  49. cv(P);
  50. }
  51.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement