This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "string/Z_Algorithm.hpp"
#pragma once #include <string> #include <vector> /* reference: https://snuke.hatenablog.com/entry/2014/12/03/214243 */ namespace ebi { std::vector<int> Z_Algorithm(const std::string &s) { int n = s.size(); std::vector<int> prefix(n); prefix[0] = n; int i = 1; int j = 0; // s[0,j], s[i,i+j] がすでに一致していることが保証されている. while (i < n) { while (i + j < n && s[j] == s[i + j]) ++j; prefix[i] = j; if (j == 0) { ++i; continue; } int k = 1; while (i + k < n && k + prefix[k] < j) { prefix[i + k] = prefix[k]; ++k; } i += k; j -= k; } return prefix; } } // namespace ebi
#line 2 "string/Z_Algorithm.hpp" #include <string> #include <vector> /* reference: https://snuke.hatenablog.com/entry/2014/12/03/214243 */ namespace ebi { std::vector<int> Z_Algorithm(const std::string &s) { int n = s.size(); std::vector<int> prefix(n); prefix[0] = n; int i = 1; int j = 0; // s[0,j], s[i,i+j] がすでに一致していることが保証されている. while (i < n) { while (i + j < n && s[j] == s[i + j]) ++j; prefix[i] = j; if (j == 0) { ++i; continue; } int k = 1; while (i + k < n && k + prefix[k] < j) { prefix[i + k] = prefix[k]; ++k; } i += k; j -= k; } return prefix; } } // namespace ebi