fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /*#include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. /*template <typename T>
  7. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. */typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef long double ld;
  11. typedef pair<ll,ll> pl;
  12. typedef pair<int,int> pii;
  13.  
  14. #define LOCAL 0
  15. #define dbg(x) cout << #x << " is " << x << "\n"
  16. #define gll(x) scanf("%d",&x)
  17. #define gll2(x,y) scanf("%d%d",&x,&y)
  18. #define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  19. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  20. #define sz(x) ((int)x.size())
  21. #define s(x) sort(x.begin(),x.end())
  22. #define all(v) v.begin(),v.end()
  23. #define rs(v) { s(v) ; r(v) ; }
  24. #define r(v) {reverse(all(v));}
  25. #define pb push_back
  26. #define f(i,n) for(int i=0;i<n;i++)
  27. #define fr(i,n) for(int i=n-1;i>=0;i--)
  28. #define rep(i,a,b) for(int i=a;i<=b;i++)
  29. #define repr(i,a,b) for(int i=a;i>=b;i--)
  30.  
  31. const ll mod = (ll)1e9 + 7;
  32. const ll inf = (ll)1e16;
  33. const ld eps = 1e-12;
  34. const ll N = (int)1e4 + 5;
  35. const ll LOGN = 19;
  36. const ld PI = 3.14159265358979323846;
  37. inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  38. inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  39. inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  40.  
  41. inline int index(char c) {
  42.     return ((int) c - (int) 'a' + 1);
  43. }
  44.  
  45. ll powers[35];
  46.  
  47. void pre()
  48. {
  49.     powers[0] = 1ll;
  50.     rep(i, 1, 30) powers[i] = powers[i - 1] * 4ll;
  51.     //for(int i = 0; i < 34; i++) cout<<invpowers[i]<<" ";
  52. }
  53.  
  54. struct node{
  55.     ll val;
  56.     int index;
  57.     node() {}
  58.     inline void merge(node l, node r)
  59.     {
  60.         if(l.val > r.val)
  61.         {
  62.             val = l.val;
  63.             index = l.index;
  64.         }
  65.         else if(l.val == r.val)
  66.         {
  67.             val = l.val;
  68.             index = min(l.index, r.index);
  69.         }
  70.         else
  71.         {
  72.             val = r.val;
  73.             index = r.index;
  74.         }
  75.     }
  76.  
  77.     inline void no_use()
  78.     {
  79.         val = LONG_LONG_MIN;
  80.         index = -1;
  81.     }
  82. };
  83.  
  84. int num[N];
  85. node segtree[4 * N];
  86.  
  87. void build(int nd, int start, int end)
  88. {
  89.     if(start == end)
  90.     {
  91.         segtree[nd].val = num[start];
  92.         segtree[nd].index = start;
  93.         return;
  94.     }
  95.     int mid = (start + end) >> 1;
  96.     build(2 * nd + 1, start, mid);
  97.     build(2 * nd + 2, mid + 1, end);
  98.     segtree[nd].merge(segtree[2 * nd + 1], segtree[2 * nd + 2]);
  99. }
  100.  
  101. node query(int nd, int start, int end, int qs, int qe)
  102. {
  103.     if(end < qs || start > qe || start > end)
  104.     {
  105.         node temp;
  106.         temp.no_use();
  107.         return temp;
  108.     }
  109.     if(start >= qs && end <= qe) return segtree[nd];
  110.     node p,q;
  111.     int mid = (start + end) >> 1;
  112.     p = query(2 * nd + 1, start, mid, qs, qe);
  113.     q = query(2 * nd + 2, mid + 1, end, qs, qe);
  114.     node ret;
  115.     ret.merge(p,q);
  116.     return ret;
  117. }
  118.  
  119. int main() {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(NULL);
  122.     if (LOCAL) {
  123.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
  124.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
  125.     }
  126.     int t;
  127.     cin>>t;
  128.     pre();
  129.     while(t--)
  130.     {
  131.         int n,q;
  132.         cin>>n>>q;
  133.         string s;
  134.         unordered_map<ll, int> mp;
  135.         f(i,n) {
  136.             cin >> s;
  137.             int len = s.length();
  138.             num[i] += len;
  139.             ll prefix_hash[len + 2] = {0};
  140.             ll suffix_hash[len + 2] = {0};
  141.             prefix_hash[0] = index(s[0]);
  142.             suffix_hash[len - 1] = index(s[len - 1]);
  143.             rep(j, 1, len - 1) {
  144.                 prefix_hash[j] = prefix_hash[j - 1] + (index(s[j]) * powers[j]);
  145.             }
  146.             //Suffix
  147.             for (int j = len - 2; j >= 0; j--) {
  148.                 suffix_hash[j] = suffix_hash[j + 1] + (index(s[j]) * powers[len - j - 1]);
  149.             }
  150.             mp[prefix_hash[len - 1]] = i;
  151. //            f(j,len) cout<<prefix_hash[j]<<" ";
  152. //            cout<<endl;
  153. //            f(j,len) cout<<suffix_hash[j]<<' ';
  154. //            cout<<endl;
  155.             //Count 1 length also;
  156.             rep(R, 1, len - 1) {
  157.                 ll fir = prefix_hash[R];
  158.                 ll sec = (suffix_hash[0] - suffix_hash[R + 1]) / powers[len - 1 - R];
  159.                 //cout<<"0th na"<<fir<<" "<<sec<<endl;
  160.                 if (fir == sec)
  161.                     num[i]++;
  162.             }
  163.             rep(L, 1, len - 1) {
  164.                 rep(R, L + 1, len - 1) {
  165.                     ll sidha = (prefix_hash[R] - prefix_hash[L - 1]) / powers[L];
  166.                     ll ulta = (suffix_hash[L] - suffix_hash[R + 1]) / powers[len - 1 - R];
  167.                     //cout<<"In: "<<sidha<<" "<<ulta<<endl;
  168.                     if (sidha == ulta)
  169.                         num[i]++;
  170.                 }
  171.             }
  172.         }
  173.         //f(i,n) cout<<num[i]<<" ";
  174.         build(0,0,n-1);
  175.         while(q--)
  176.         {
  177.             string l,r;
  178.             cin>>l>>r;
  179.             int len = l.length();
  180.             ll prefix_hash[len + 2] = {0};
  181.             prefix_hash[0] = index(l[0]);
  182.             rep(j,1,len - 1)
  183.             {
  184.                 prefix_hash[j] = (prefix_hash[j - 1]+ (index(l[j]) * powers[j]));
  185.             }
  186.             int L = mp[prefix_hash[len - 1]];
  187.             len = r.length();
  188.             ll prefix_hash2[len + 2] = {0};
  189.             prefix_hash2[0] = index(r[0]);
  190.             rep(j, 1, len - 1)
  191.             {
  192.                 prefix_hash2[j] = prefix_hash2[j - 1] + (index(r[j]) * powers[j]);
  193.             }
  194.             int R = mp[prefix_hash2[len - 1]];
  195.             node ans = query(0, 0, n - 1, L, R);
  196.             cout<<ans.index + 1<<"\n";
  197.         }
  198.     }
  199.     return 0;
  200. }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
1
5 5
aaaaa
abaabc
cbbaca
abccba
abca
aaaaa abca
cbbaca abccba
abaabc abccba
abccba abca
abaabc abccba
stdout
copy 
1
4
2
4
2
https://ideone.com/qz98Xa
language:
C++ (gcc 8.3)
created:
5 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!