Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cmath>
- #include <algorithm>
- #include <cstdlib>
- #include <cstring>
- #include <vector>
- #include <string>
- #include <set>
- using namespace std;
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- char *str = (char*)malloc(10001);
- scanf("%s", str);
- int len = strlen(str);
- vector<long long> h(len);
- vector<long long> p(len);
- h[0] = str[0]-'a'+1;
- p[0] = 1;
- for (int i = 1; i < len; i++) {
- p[i] = p[i-1] * 3137;
- }
- for (int i = 1; i < len; i++) {
- h[i] = h[i-1] + (str[i]-'a'+1)*p[i];
- }
- long long count = 1;
- vector<long long> hs(len);
- for (int i = 1; i < len; i++) {
- for (int j = 0; j + i - 1 < len; j++) {
- long long hh = p[len - j - 1]*(h[j + i - 1] - (j == 0 ? 0 : h[j - 1]));
- hs[j] = hh;
- }
- sort (hs.begin(), hs.begin() + (len - i + 1));
- long long last = hs[0];
- count++;
- for (int j = 1; j < len - i + 1; j++) {
- if (last != hs[i]) {
- last = hs[i];
- count++;
- }
- }
- }
- printf("%lld", count);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement