Advertisement
Guest User

Untitled

a guest
Jun 26th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.04 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <vector>
  7. #include <string>
  8. #include <set>
  9.  
  10. using namespace std;
  11.  
  12. int main()
  13. {
  14. #ifndef ONLINE_JUDGE
  15.     freopen("input.txt", "r", stdin);
  16.     freopen("output.txt", "w", stdout);
  17. #endif
  18.     char *str = (char*)malloc(10001);
  19.     scanf("%s", str);
  20.     int len = strlen(str);
  21.     vector<long long> h(len);
  22.     vector<long long> p(len);
  23.     h[0] = str[0]-'a'+1;
  24.     p[0] = 1;
  25.     for (int i = 1; i < len; i++) {
  26.         p[i] = p[i-1] * 3137;
  27.     }
  28.     for (int i = 1; i < len; i++) {
  29.         h[i] = h[i-1] + (str[i]-'a'+1)*p[i];
  30.     }
  31.     long long count = 1;
  32.     vector<long long> hs(len);
  33.     for (int i = 1; i < len; i++) {
  34.         for (int j = 0; j + i - 1 < len; j++) {
  35.             long long hh = p[len - j - 1]*(h[j + i - 1] - (j == 0 ? 0 : h[j - 1]));
  36.             hs[j] = hh;
  37.         }
  38.         sort (hs.begin(), hs.begin() + (len - i + 1));
  39.         long long last = hs[0];
  40.         count++;
  41.         for (int j = 1; j < len - i + 1; j++) {
  42.             if (last != hs[i]) {
  43.                 last = hs[i];
  44.                 count++;
  45.             }
  46.         }
  47.     }
  48.     printf("%lld", count);
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement