Submit Info #2681

Problem Lang User Status Time Memory
Z Algorithm cpp suzuken AC 32 ms 3.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 7 ms 0.65 MiB
example_01 AC 5 ms 0.63 MiB
example_02 AC 7 ms 0.59 MiB
example_03 AC 5 ms 0.65 MiB
random_00 AC 26 ms 3.43 MiB
random_01 AC 31 ms 3.84 MiB
random_02 AC 10 ms 1.09 MiB
random_03 AC 28 ms 3.68 MiB
random_04 AC 20 ms 2.63 MiB
random_05 AC 22 ms 2.90 MiB
random_06 AC 32 ms 3.88 MiB
random_07 AC 12 ms 1.42 MiB
random_08 AC 21 ms 2.61 MiB
random_09 AC 12 ms 1.51 MiB

#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; using ll=long long; typedef unsigned long long int ull; typedef pair<ll,ll> P; template<class T> using V=vector<T>; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); //const ll mod=998244353; const ll mod=1000000007; //ios_base::sync_with_stdio(false); //cin.tie(NULL); ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;} ll lcm(ll c,ll d){return c/gcd(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } V<int> z_algo(const string &s){ int n=s.size(); V<int> prefix(n); for(int i=1,j=0;i<n;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<n&&s[k]==s[i+k])k++; prefix[i]=k; j=i; } } prefix[0]=n; return prefix; } int main(){ string s; cin>>s; V<int> d=z_algo(s); for(int v:d)cout<<v<<" "; cout<<endl; }