test/yosupo_z_algorithm.test.cpp

• View this file on GitHub
• Last update: 2024-02-10 15:48:26+09:00
• Problem: https://judge.yosupo.jp/problem/zalgorithm

Depends on

• string/z_algorithm.hpp

Code

#define PROBLEM   "https://judge.yosupo.jp/problem/zalgorithm"

#include "../string/z_algorithm.hpp"


#include <bits/stdc++.h>
using namespace std;
using ll=long long;



int main() {
    ios::sync_with_stdio(false);
  cin.tie(0);
 
 string S;cin>>S;
 Z_algorithm z;
 z.build(S);

 for(ll i=0;i<z.size();i++) {
  cout<<z[i]<<" ";
 }
 cout<<endl;
 
}

#line 1 "test/yosupo_z_algorithm.test.cpp"
#define PROBLEM   "https://judge.yosupo.jp/problem/zalgorithm"

#line 2 "string/z_algorithm.hpp"
#include<vector> 
#include<string>
using namespace std;


struct Z_algorithm
{
  vector< int > prefix;

  void build(const string &s)
  {
    prefix.assign(s.size(), 0);
    for(int i = 1, j = 0; i < s.size(); i++) {
      if(i + prefix[i - j] < j + prefix[j]) {
        prefix[i] = prefix[i - j];
      } else {
        int k = max(0, j + prefix[j] - i);
        while(i + k < s.size() && s[k] == s[i + k]) ++k;
        prefix[i] = k;
        j = i;
      }
    }
    prefix[0] = (int) s.size();
  }

  int operator[](const int k) const
  {
    return (prefix[k]);
  }

  size_t size()
  {
    return(prefix.size());
  }
};
#line 4 "test/yosupo_z_algorithm.test.cpp"


#include <bits/stdc++.h>
using namespace std;
using ll=long long;



int main() {
    ios::sync_with_stdio(false);
  cin.tie(0);
 
 string S;cin>>S;
 Z_algorithm z;
 z.build(S);

 for(ll i=0;i<z.size();i++) {
  cout<<z[i]<<" ";
 }
 cout<<endl;
 
}

Back to top page