fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2.  
  3. #include<bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/trie_policy.hpp>
  6. //#include <ext/rope>
  7.  
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  10. //#pragma GCC target("avx,avx2,fma")
  11.  
  12. //using namespace std;
  13. //using namespace __gnu_pbds;
  14. //using namespace __gnu_cxx;
  15.  
  16. #define fi first
  17. #define se second
  18. #define TASK "test"
  19. #define pb push_back
  20. #define EL cout << endl
  21. #define Ti20_ntson int main()
  22. #define in(x) cout << x << endl
  23. #define all(x) (x).begin(),(x).end()
  24. #define getbit(x, i) (((x) >> (i)) & 1)
  25. #define cntbit(x) __builtin_popcount(x)
  26. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  27. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  28. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef vector<int> vi;
  34. typedef pair<int,int> vii;
  35. typedef unsigned long long ull;
  36. typedef vector<vector<int>> vvi;
  37.  
  38. const int N = 1e6 + 5;
  39. const int oo = INT_MAX;
  40. const ll mod = 1e9 + 7;
  41. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  42. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  43. const int Base = 311;
  44.  
  45. string T, s;
  46. int n;
  47. long long Ans = 0, Pow[100];
  48. int pre[N], suf[N];
  49.  
  50. struct HASH {
  51.     long long Hash[100];
  52.     int n;
  53.  
  54.     void build(int _n, string s) {
  55.         n = _n;
  56.         for (int i = 1; i <= n; i++)
  57.             Hash[i] = (Hash[i - 1] * Base + s[i - 1] - 'a' + 1) % mod;
  58.     }
  59.  
  60.     int Get(int l, int r) {
  61.         if (r > n || l < 1) return -1;
  62.         return (Hash[r] - Hash[l - 1] * Pow[r - l + 1] + mod * mod) % mod;
  63.     }
  64.  
  65. }HashT, HashS;
  66.  
  67. inline void Read_Input() {
  68.     Pow[0] = 1;
  69.     FOR(i, 1, 80)
  70.         Pow[i] = Pow[i - 1] * Base % mod;
  71.     cin >> T;
  72.     int nt = T.size();
  73.     HashT.build(nt, T);
  74.     int __;
  75.     cin >> __;
  76.     FOR(i, 1, __) {
  77.         cin >> s;
  78.         n = s.size();
  79.         HashS.build(n, s);
  80. //        cout << HashT.Get(1, 2) << " " << HashS.Get(2, 3) << endl;
  81.         FOR(j, 1, n - nt + 1)
  82.             if (HashS.Get(j, j + nt - 1) == HashT.Get(1, nt)) Ans += 2 * __;
  83.  
  84.         FOR(j, 1, nt)
  85.             if (HashT.Get(j, nt) == HashS.Get(1, nt - j + 1)) {
  86. //                cout << "SUF " << nt - j + 1 << endl;
  87.                 suf[nt - j + 1]++;
  88.             }
  89.          FOR(j, 2, nt)
  90.             if (HashT.Get(j, nt) == HashS.Get(1, nt - j + 1))
  91.                 Ans += pre[j - 1];
  92.         FOR(j, 1, nt)
  93.             if (HashT.Get(1, j) == HashS.Get(n - j + 1, n))
  94.                 Ans += suf[nt - j];
  95.         FOR(j, 1, nt - 1)
  96.             if (HashT.Get(1, j) == HashS.Get(n - j + 1, n)) {
  97. //                cout << "PRE " << j << endl;
  98.                 pre[j]++;
  99.             }
  100. //        cout << "ANS " << Ans << endl << endl;
  101.     }
  102. }
  103.  
  104. inline void Solve() {
  105.     cout << Ans;
  106. }
  107.  
  108. Ti20_ntson {
  109. //    freopen(TASK".INP","r",stdin);
  110. //    freopen(TASK".OUT","w",stdout);
  111.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  112.     int T = 1;
  113.     while (T -- ) {
  114.         Read_Input();
  115.         Solve();
  116.     }
  117. }
  118.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
55083008
https://ideone.com/SJ19Qz
language:
C++14 (gcc 8.3)
created:
30 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!