Advertisement
Malinovsky239

Untitled

Nov 17th, 2011
170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4.  
  5. typedef long long LL;
  6.  
  7. #define L int(1e6 + 5)
  8. #define P LL(1e9 + 7)
  9.  
  10. using namespace std;
  11.  
  12. char s[L];
  13. LL hash[L], a[L], p[L];
  14. int t, k;
  15.  
  16. LL count_hash(int l, int r) {
  17.     if (!l) return hash[r];
  18.     return hash[r] - hash[l - 1] * p[r - l + 1];
  19. }
  20.  
  21. int main() {
  22.     freopen("autoreg.in", "r", stdin);
  23.     freopen("autoreg.out", "w", stdout);
  24.  
  25.     gets(s);
  26.     int l = strlen(s);
  27.     scanf("%d", &k);
  28.  
  29.     hash[0] = s[0];
  30.     for (int i = 1; i < l; i++)
  31.         hash[i] = hash[i - 1] * P + s[i];                      
  32.  
  33.     p[0] = 1;
  34.     for (int i = 1; i < l; i++)
  35.         p[i] = p[i - 1] * P;
  36.  
  37.     for (int i = k - 1; i < l; i++) {
  38.         a[t++] = count_hash(i - k + 1, i);
  39.     }      
  40.  
  41.     sort(a, a + t);
  42.  
  43.     for (int i = 1; i < t; i++)
  44.         if (a[i] == a[i - 1]) {
  45.             puts("YES");
  46.             return 0;
  47.         }
  48.  
  49.     puts("NO");
  50.    
  51.     return 0;
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement