Advertisement
biznesman

Untitled

Aug 3rd, 2020
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5 + 10;
  6. const int INF = 1e9 + 7;
  7. const double EPS = 1e-10;
  8. const double PI = acosl(-1);
  9. const int P = 41;
  10. const int MOD = 1e9 + 7;
  11.  
  12. int p[3000], h[3000], ans;
  13. string s;
  14.  
  15. int main() {
  16. //ifstream cin("input.txt");
  17. //ofstream cout("output.txt");
  18. ios_base::sync_with_stdio(false);
  19. cin.tie(0);
  20. cout.tie(0);
  21. cin >> s;
  22. p[0] = 1;
  23. int n = s.size();
  24. for (int i = 1; i <= n; i++) {
  25. p[i] = (1ll * p[i - 1] * P) % MOD;
  26. }
  27. h[0] = (s[0] - 'a' + 1);
  28. for (int i = 1; i < n; i++) {
  29. h[i] = (1ll * h[i - 1] + (1ll * (s[i] - 'a' + 1) * p[i]) % MOD) % MOD;
  30. }
  31. vector<long long> check;
  32. for (int i = 0; i < n; i++) {
  33. for (int j = i; j < n; j++) {
  34. if (j) {
  35. check.push_back((1ll * (h[j] - h[i - 1]) % MOD * p[n - i - 1]) % MOD);
  36. } else {
  37. check.push_back((1ll * h[j] * p[n - i - 1]) % MOD);
  38. }
  39. }
  40. }
  41. sort(check.begin(), check.end());
  42. check.erase(unique(check.begin(), check.end()), check.end());
  43. ans += (int)check.size();
  44. cout << ans;
  45. return 0;
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement