Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3690

Problem Lang User Status Time Memory
Z Algorithm cpp14 shiro53 AC 29 ms 3.88 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
example_01 AC 5 ms 0.63 MiB
example_02 AC 5 ms 0.66 MiB
example_03 AC 4 ms 0.62 MiB
random_00 AC 26 ms 3.39 MiB
random_01 AC 29 ms 3.88 MiB
random_02 AC 9 ms 1.00 MiB
random_03 AC 28 ms 3.68 MiB
random_04 AC 22 ms 2.67 MiB
random_05 AC 21 ms 2.89 MiB
random_06 AC 29 ms 3.76 MiB
random_07 AC 11 ms 1.34 MiB
random_08 AC 19 ms 2.52 MiB
random_09 AC 11 ms 1.43 MiB

#include <bits/stdc++.h> using namespace std; template <class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T &a, T b) { if(a > b) { a = b; return 1; } return 0; } typedef long long int ll; #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define endl "\n" const double EPS = 1e-7; const int INF = 1 << 30; const ll LLINF = 1LL << 60; const double PI = acos(-1); const int MOD = 1000000007; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; //------------------------------------- // すべて0-indexed // n := |S| とする。 // s[i,j] := sの[i,j]の範囲の連続部分文字列とする。このとき、 // s[0, n-1](= s)とs[i, n-1]の最長共通接頭辞の長さを記録した配列を返す。 // 計算量はO(|S|) vector<int> z_algo(const string &s) { int c = 0, n = s.size(); vector<int> z(n, 0); for(int i = 1; i < n; i++) { if(i + z[i - c] < c + z[c]) { z[i] = z[i - c]; } else { int j = max(0, c + z[c] - i); while(i + j < n && s[j] == s[i + j]) { j++; } z[i] = j; c = i; } } z[0] = n; return z; } int main() { cin.tie(0); ios::sync_with_stdio(false); string s; cin >> s; auto z = z_algo(s); for(int i = 0; i < z.size(); i++) { cout << z[i] << ' '; } cout << endl; }