Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "testlib.h"
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> prefix_function(string s) {
- int n = (int)s.length();
- vector<int> pi(n);
- for(int i = 1; i < n; ++i) {
- int j = pi[i - 1];
- while(j > 0 && s[i] != s[j])
- j = pi[j - 1];
- if(s[i] == s[j]) ++j;
- pi[i] = j;
- }
- return pi;
- }
- vector<int> z_function(string s) {
- int n = (int)s.length();
- vector<int> z(n);
- for(int i = 1, l = 0, r = 0; i < n; ++i) {
- if(i <= r)
- z[i] = min(r - i + 1, z[i - l]);
- while(i + z[i] < n && s[z[i]] == s[i + z[i]])
- ++z[i];
- if(i + z[i] - 1 > r)
- l = i, r = i + z[i] - 1;
- }
- return z;
- }
- long long comp(string s){
- auto a = prefix_function(s);
- auto b = z_function(s);
- long long t = 0;
- for(int i = 0; i < s.size(); i++){
- t += 1ll * a[i] * b[i];
- }
- return t;
- }
- int main(int argc, char * argv[]){
- registerTestlibCmd(argc, argv);
- long long N = inf.readLong();
- long long K = inf.readLong();
- string G = ouf.readString();
- if(G.size() > K){
- quitf(_wa, "incorrect length of the string");
- }
- for(int i = 0; i < G.size(); i++){
- ensure(G[i] <= 'z' && G[i] >= 'a');
- }
- if(comp(G) == N){
- quitf(_ok, "ok");
- }
- else {
- quitf(_wa, "wa");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement