fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(a) (a).begin(), (a).end()
  4. #define dbg_line(x) cout << (x) << '\n'
  5. #define dbg(x) cout << x << " "
  6.  
  7. using namespace std;
  8.  
  9. // <--> Report constants <-->
  10.  
  11. typedef pair<int, int> pii;
  12. const int max_n = 1e5 + 5;
  13. const ll inf = 1e9;
  14. const ll m_inf = -1e9;
  15. const ll mod = 1e9 + 7;
  16. const int base = 32;
  17.  
  18. // <--> Report variables <-->
  19.  
  20. ll pref[max_n];
  21. ll mult[max_n];
  22.  
  23. // <--> Main Code is Here <-->
  24.  
  25. void buildHash(string s){
  26.     pref[0] = 0;
  27.     mult[0] = 1;
  28.     int n = (int)s.size();
  29.     for (int i = 1; i <= n; i++){
  30.         pref[i] = (pref[i - 1] * base + s[i - 1] - 'a' + 1) % mod;
  31.         mult[i] = (mult[i - 1] * base) % mod;
  32.     }
  33. }
  34.  
  35. // ll getHashString(string s){
  36. //     ll res = 0;
  37. //     for (char c : s){
  38. //         res = (res * base + c - 'a' + 1) % mod;
  39. //     }
  40. //     return res;
  41. // }
  42.  
  43. ll getHash(int l, int r){
  44.     return (pref[r] - (pref[l - 1] * mult[r - l + 1]) % mod + mod) % mod;
  45. }
  46.  
  47. void setIO(){
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     cout.tie(NULL);
  51. }
  52.  
  53. void call_file(){
  54.     freopen("input.txt","r",stdin);
  55.     freopen("output.txt","w",stdout);
  56. }
  57.  
  58. int main(){
  59.     setIO();
  60.     call_file();
  61.     string s;
  62.     cin >> s;
  63.     buildHash(s);
  64.     vector<int> tmp;
  65.     for (int i = 1; i <= (int)s.size(); i++){
  66.         if (getHash(1, i) == getHash(s.size() - i + 1, s.size())){
  67.             tmp.push_back(i);
  68.         }
  69.     }
  70.     cout << (int)tmp.size() << '\n';
  71.     vector<pii> v;
  72.     for (int x : tmp){
  73.         int l = 1;
  74.         int cnt = 0;
  75.         int hashRes = getHash(1, x);
  76.         for (int r = x; r <= s.size(); r++){
  77.             if (getHash(l, r) == hashRes){
  78.                 cnt++;
  79.             }
  80.             ++l;
  81.         }
  82.         v.push_back({x, cnt});
  83.     }
  84.     for (pii x : v){
  85.         cout << x.first << " " << x.second << '\n';
  86.     }
  87. }
  88.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tnOjQw
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!