fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define rep(i, a, b) for(int i=(a); i<(b); i++)
  5. #define repi(i, a, b) for(int i=(a); i>(b); i--)
  6. #define db(x) (cerr << #x << ": " << (x) << '\n')
  7. #define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
  8. #define tests(t) int t; cin >> t; while(t--)
  9. #define iceil(n, x) (((n) + (x) - 1) / (x))
  10. #define ll long long
  11. #define gcd __gcd
  12. #define eb emplace_back
  13. #define pb push_back
  14. #define pf push_front
  15. #define pob pop_back
  16. #define pof pop_front
  17. #define sz size()
  18. #define all(v) (v).begin(), (v).end()
  19. #define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
  20. #define pii pair<int, int>
  21. #define vi vector<int>
  22. #define vpii vector<pii>
  23. #define vvi vector<vi>
  24. #define fi first
  25. #define se second
  26. #define pqueue priority_queue
  27. #define bitcount(x) __builtin_popcount(x)
  28. #define cps CLOCKS_PER_SEC
  29. #define PI acos(-1.0)
  30. #define EPS 1e-9
  31. #define mod 1000000007
  32. using namespace std;
  33.  
  34. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  35. template <typename Arg1>
  36. void __f(const char* name, Arg1&& arg1){
  37.     cerr << name << " : " << arg1 << '\n';
  38. }
  39. template <typename Arg1, typename... Args>
  40. void __f(const char* names, Arg1&& arg1, Args&&... args){
  41.     const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  42. }
  43.  
  44. template<typename T1, typename T2>
  45. ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << '(' << p.fi << ", " << p.se << ')'; }
  46.  
  47. template<typename T>
  48. void printv(const T& v) { for(auto i : v) cerr << i << ' '; cerr << '\n'; }
  49.  
  50. template<typename T>
  51. using minpq = priority_queue<T, vector<T>, greater<T>>;
  52.  
  53. template<typename T>
  54. using maxpq = priority_queue<T>;
  55.  
  56. //All indexing is 0-based
  57. using namespace __gnu_pbds;
  58. template<class key, class cmp = std::less<key>>
  59. using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  60. //methods: find_by_order(k); & order_of_key(k);
  61. //To make it an ordered_multiset, use pairs of (value, time_of_insertion)
  62. //to distinguish values which are similar
  63.  
  64. template<class key, class value, class cmp = std::less<key>>
  65. using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  66.  
  67. //Returns no. of values x for which ceil(n / x) == y (y must be > 1).
  68. inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
  69.  
  70. //Returns no. of values x for which floor(n / x) == y
  71. inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
  72.  
  73. //a and b are assumed to be taken modulo p
  74. inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
  75. inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
  76. inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
  77.  
  78. #define N 1000005
  79. #define int ll
  80. // #define trace(...) 42
  81.  
  82. //Link: https://c...content-available-to-author-only...s.com/string/suffix-automaton.html
  83.  
  84. string s; int n; 
  85.  
  86. struct state {
  87.     int len, link; //len: Length of longest string ending at the state
  88.                    //link: suffix link
  89.     bool terminal; //Is the state terminal ?
  90.     map<char, int> next;
  91. };
  92.  
  93. state st[N << 1];
  94. int cnt, last;
  95.  
  96. void init(int cur) {
  97.     st[cur].len = 0;
  98.     st[cur].link = -1;
  99.     st[cur].terminal = 0;
  100.     st[cur].next.clear();
  101. }
  102.  
  103. void sa_init() {
  104.     cnt = 0;
  105.     //source node is at index 0.
  106.     // st[0].len = 0, st[0].link = -1;
  107.     // st[0].terminal = 0;
  108.     // st[0].next.clear();
  109.     init(0);
  110.     last = 0;
  111.     cnt++;
  112. }
  113.  
  114. void sa_extend(char c) {
  115.     int cur = cnt++;
  116.     init(cur);
  117.     st[cur].len = st[last].len + 1;
  118.     int p = last;
  119.     while(p != -1 && !st[p].next.count(c)) {
  120.         st[p].next[c] = cur;
  121.         p = st[p].link;
  122.     }
  123.     if(p == -1) {
  124.         st[cur].link = 0;
  125.     }
  126.     else {
  127.         int q = st[p].next[c];
  128.         if(st[q].len == st[p].len + 1) {
  129.             st[cur].link = q;
  130.         }
  131.         else {
  132.             int clone = cnt++;
  133.             st[clone].terminal = 0;
  134.             st[clone].len = st[p].len + 1;
  135.             st[clone].link = st[q].link;
  136.             st[clone].next = st[q].next;
  137.             st[cur].link = st[q].link = clone;
  138.             while(p != -1 && st[p].next[c] == q) {
  139.                 st[p].next[c] = clone;
  140.                 p = st[p].link;
  141.             }
  142.         }
  143.     }
  144.     last = cur;
  145. }
  146.  
  147. void find_terminals() {
  148.     int p = last;
  149.     while(p) {
  150.         st[p].terminal = 1;
  151.         p = st[p].link;
  152.     }
  153. }
  154.  
  155. //O(N lg K), where K is the size of the alphabet
  156. void SuffixAutomaton() {
  157.     sa_init();
  158.     n = s.size();
  159.     for(int i = 0; i < n; i++) {
  160.         sa_extend(s[i]);
  161.     }
  162.     find_terminals();
  163. }
  164.  
  165. void printSA() {
  166.     for(int i = 0; i < cnt; i++) {
  167.         cout << "i: " << i << '\n';
  168.         cout << "Terminal: " << st[i].terminal << '\n';
  169.         cout << "Transitions:\n"; 
  170.         for(auto p : st[i].next) {
  171.             cout << p.first << " -> " << p.second << '\n';
  172.         }
  173.         cout << "Suf Link: " << st[i].link << '\n';
  174.         cout << '\n';
  175.     }
  176. }
  177.  
  178. int tot[N], pret[N];
  179. int ans[N], pre[N];
  180. bool vis[N];
  181.  
  182. void dfs(int cur) {
  183.     vis[cur] = 1;
  184.     if(cur) {
  185.         int l, r;
  186.         l = st[st[cur].link].len + 1;
  187.         r = st[cur].len;
  188.         ans[l]++, ans[r+1]--;
  189.         // trace(l, r);
  190.     }
  191.     for(auto p : st[cur].next) {
  192.         int i = p.se;
  193.         if(!vis[i]) dfs(i);
  194.     }
  195. }
  196.  
  197. int norm(int x) {
  198.     if(x < 0) x += mod;
  199.     if(x >= mod) x -= mod;
  200.     return x;
  201. }
  202.  
  203. void prep() {
  204.     SuffixAutomaton();
  205.     fill_n(ans, n + 5, 0);
  206.     fill_n(vis, cnt, 0);
  207.     dfs(0);
  208.  
  209.     for(int i = 1; i <= n; i++)
  210.         ans[i] += ans[i-1];
  211.  
  212.     for(int i = 0; i <= n; i++) {
  213.         // trace(i, ans[i]);
  214.         pre[i] = ans[i];
  215.         if(i) pre[i] = add(pre[i], pre[i-1]);
  216.     }
  217.     assert(!pre[0]);
  218. }
  219.  
  220. main()
  221. {   
  222.     #ifdef CP
  223.         freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  224.      // freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  225.     #endif
  226.     sync;
  227.     clock_t clk = clock();
  228.     cerr << "I will return...\n";
  229.  
  230.     rep(i, 0, N) {
  231.         if(i == 0) tot[i] = pre[i] = 1;
  232.         else {
  233.             tot[i] = mul(26, tot[i-1]);
  234.             pret[i] = add(pret[i-1], tot[i]);
  235.         }
  236.     }
  237.  
  238.     int oo = 1;
  239.     tests(t) {
  240.         // trace(t);
  241.         cout << "Case " << oo++ << ":\n";
  242.         cin >> s; n = s.size();
  243.         prep();
  244.         int q; cin >> q;
  245.         while(q--) {
  246.             int l, r; cin >> l >> r;
  247.             --l;
  248.             int ans = pret[r];
  249.             ans = sub(ans, pret[l]);
  250.             ans = sub(ans, sub(pre[r], pre[l]));
  251.             // trace(sub(pre[r], pre[l]));
  252.             cout << ans << '\n';
  253.         }
  254.     }
  255.  
  256.     cerr << "...don't you ever hang your head.\n";
  257.     cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
  258. }
  259.  
  260. //Compile using:
  261. //g++ -o filename.exe --std=c++11 filename.cpp
  262. //Use -D CP for defining a macro CP in the local environment
  263.  
  264.  
  265.  
Success #stdin #stdout #stderr 0.05s 160060KB
comments (?)
stdin
copy 
3
abcab
5
1 2
2 2
3 5
1 1
1 5
abbab
5
1 2
2 2
3 5
1 1
1 5
aaaaa
5
1 1
2 2 
3 3
4 4
5 5
stdout
copy 
Case 1:
696
673
12355922
23
12356618
Case 2:
697
673
12355922
24
12356619
Case 3:
25
675
17575
456975
11881375
stderr
copy 
I will return...
...don't you ever hang your head.
Time (in ms): 7.54
https://ideone.com/yScFoq
language:
C++14 (gcc 8.3)
created:
4 years 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!