Advertisement
Guest User

CF_BR86_B

a guest
Sep 9th, 2011
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5.  
  6. #include <iostream>
  7. #include <iomanip>
  8. #include <vector>
  9. #include <string>
  10. #include <algorithm>
  11. #include <set>
  12. #include <map>
  13.  
  14. using namespace std;
  15.  
  16. #define sqr(x) ((x)*(x))
  17. #define pb push_back
  18. #define mp make_pair
  19. #define forn(i, n) for (i = 0; i < (int)(n); ++i)
  20.  
  21. typedef unsigned long long ll;
  22. typedef pair <int, int> pii;
  23. typedef vector <int> vi;
  24.  
  25. const ll P = 100000 + 3;
  26. const int maxlen = 2000 + 5;
  27.  
  28. ll pdeg[maxlen];
  29. ll t_hash[maxlen];
  30.  
  31. map <ll, bool> mapa;
  32.  
  33. int main()
  34. {
  35. #ifndef ONLINE_JUDGE
  36.         freopen("input.txt", "r", stdin);
  37.         freopen("output.txt", "w", stdout);
  38. #endif
  39.  
  40.         int ans = 0;
  41.         string t, sbegin, send;
  42.         cin >> t >> sbegin >> send;
  43.  
  44.         int i, j, n = t.length();
  45.         pdeg[0] = 1;
  46.         for(i = 1; i <= n; ++i) {
  47.                 pdeg[i] = pdeg[i - 1]*P;
  48.         }
  49.  
  50.         ll h1, h2;
  51.         h1 = h2 = 0;
  52.         forn(i, n) {
  53.                 if (i)
  54.                         t_hash[i] = t_hash[i - 1]*P;
  55.                 else
  56.                         t_hash[i] = 0;
  57.                 t_hash[i] += t[i] - 'a';
  58.         }
  59.  
  60.         int l1 = sbegin.length(), l2 = send.length();
  61.         if (l1 > n || l2 > n) {
  62.                 puts("0");
  63.                 return 0;
  64.         }
  65.         forn(i, l1) {
  66.                 h1 *= P;
  67.                 h1 += sbegin[i] - 'a';
  68.         }
  69.         forn(i, l2) {
  70.                 h2 *= P;
  71.                 h2 += send[i] - 'a';
  72.         }
  73.  
  74.         for (i = 0; i <= n - l1; ++i) {
  75.                 if (h1 != t_hash[i + l1 - 1] - t_hash[i - 1]*pdeg[l1])
  76.                         continue;
  77.                 for (j = i; j <= n - l2; ++j) {
  78.                         if (h2 != t_hash[j + l2 - 1] - t_hash[j - 1]*pdeg[l2])
  79.                                 continue;
  80.                         ll h = t_hash[j + l2 - 1] - t_hash[i - 1]*pdeg[j + l2 - i];
  81.                         if (!mapa[h]) {
  82.                                 mapa[h] = true;
  83.                                 ++ans;
  84.                         }
  85.                 }
  86.         }
  87.         cout << ans;
  88.         return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement