Advertisement
scottish_esquire

Количество разных подстрок

Sep 8th, 2022
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <unordered_set>
  5.  
  6.  
  7. // Задача № 2. Количество разных подстрок
  8. // Задача найти в строке число всех подстрок. Пустая строка также учитывается.
  9.  
  10. // Тест
  11. // Входные данные:
  12. // abc
  13. // Выходные данные:
  14. // 7
  15.  
  16. // Входные данные:
  17. // ababab
  18. // Выходные данные:
  19. // 12
  20.  
  21. int mod = 1000000007;
  22.  
  23. void forward (std::string s, int k, std::unordered_set<int> &sh, int j) {
  24.     int h = 0;
  25.     int m = 1;
  26.     for (int i = j; i < s.length(); i++) {
  27.         char c = s[i];
  28.         int x = (int) (c - 'a' + 1);
  29.         h = (h + m * x) % mod;
  30.         sh.insert(h);
  31.         m = (m * k) % mod;
  32.     }
  33. }
  34.  
  35. int main() {
  36.     std::string s;
  37.     std::unordered_set<int> sh;
  38.     int f = 0;
  39.     int b = 0;
  40.     int k = 31;
  41.     std::cin >> s;
  42.     for (int i = 0; i < s.length(); i++) {
  43.         forward(s, k, sh, i);
  44.     }
  45.     std::cout << sh.size() + 1;
  46. }
  47.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement