Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cmath>
- #include <cstring>
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <set>
- #include <map>
- using namespace std;
- #define sqr(x) ((x)*(x))
- #define pb push_back
- #define mp make_pair
- #define forn(i, n) for (i = 0; i < (int)(n); ++i)
- typedef unsigned long long ll;
- typedef pair <int, int> pii;
- typedef vector <int> vi;
- const ll P = 100000 + 3;
- const int maxlen = 2000 + 5;
- ll pdeg[maxlen];
- ll t_hash[maxlen];
- map <ll, bool> mapa;
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int ans = 0;
- string t, sbegin, send;
- cin >> t >> sbegin >> send;
- int i, j, n = t.length();
- pdeg[0] = 1;
- for(i = 1; i <= n; ++i) {
- pdeg[i] = pdeg[i - 1]*P;
- }
- ll h1, h2;
- h1 = h2 = 0;
- forn(i, n) {
- if (i)
- t_hash[i] = t_hash[i - 1]*P;
- else
- t_hash[i] = 0;
- t_hash[i] += t[i] - 'a';
- }
- int l1 = sbegin.length(), l2 = send.length();
- if (l1 > n || l2 > n) {
- puts("0");
- return 0;
- }
- forn(i, l1) {
- h1 *= P;
- h1 += sbegin[i] - 'a';
- }
- forn(i, l2) {
- h2 *= P;
- h2 += send[i] - 'a';
- }
- for (i = 0; i <= n - l1; ++i) {
- if (h1 != t_hash[i + l1 - 1] - t_hash[i - 1]*pdeg[l1])
- continue;
- for (j = i; j <= n - l2; ++j) {
- if (h2 != t_hash[j + l2 - 1] - t_hash[j - 1]*pdeg[l2])
- continue;
- ll h = t_hash[j + l2 - 1] - t_hash[i - 1]*pdeg[j + l2 - i];
- if (!mapa[h]) {
- mapa[h] = true;
- ++ans;
- }
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement