Advertisement
tsypko

Untitled

Mar 5th, 2017
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include "testlib.h"
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. vector<int> prefix_function(string s) {
  8. int n = (int)s.length();
  9. vector<int> pi(n);
  10. for(int i = 1; i < n; ++i) {
  11. int j = pi[i - 1];
  12. while(j > 0 && s[i] != s[j])
  13. j = pi[j - 1];
  14. if(s[i] == s[j]) ++j;
  15. pi[i] = j;
  16. }
  17. return pi;
  18. }
  19.  
  20. vector<int> z_function(string s) {
  21. int n = (int)s.length();
  22. vector<int> z(n);
  23. for(int i = 1, l = 0, r = 0; i < n; ++i) {
  24. if(i <= r)
  25. z[i] = min(r - i + 1, z[i - l]);
  26. while(i + z[i] < n && s[z[i]] == s[i + z[i]])
  27. ++z[i];
  28. if(i + z[i] - 1 > r)
  29. l = i, r = i + z[i] - 1;
  30. }
  31. return z;
  32. }
  33.  
  34. long long comp(string s){
  35. auto a = prefix_function(s);
  36. auto b = z_function(s);
  37. long long t = 0;
  38. for(int i = 0; i < s.size(); i++){
  39. t += 1ll * a[i] * b[i];
  40. }
  41. return t;
  42. }
  43.  
  44.  
  45. int main(int argc, char * argv[]){
  46. registerTestlibCmd(argc, argv);
  47. long long N = inf.readLong();
  48. long long K = inf.readLong();
  49.  
  50. string G = ouf.readString();
  51.  
  52.  
  53. if(G.size() > K){
  54. quitf(_wa, "incorrect length of the string");
  55. }
  56.  
  57. for(int i = 0; i < G.size(); i++){
  58. ensure(G[i] <= 'z' && G[i] >= 'a');
  59. }
  60. if(comp(G) == N){
  61. quitf(_ok, "ok");
  62. }
  63. else {
  64. quitf(_wa, "wa");
  65. }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement