main.cpp (1739B)
1 #include <iostream> 2 #include <cmath> 3 4 using namespace std; 5 6 7 long long incremental(long long prior, unsigned char current, unsigned char leaving, long long high) { 8 9 long long lv = (unsigned char)leaving - 'a' + 1; 10 long long nw = (unsigned char)current - 'a' + 1; 11 12 long long q = 1000000007; 13 long long d = 26; 14 prior = (prior - lv * high % q + q) % q; 15 prior = (prior * d + (nw)) % q; 16 return prior; 17 18 } 19 20 long long hashPattern(string& input) { 21 long long q = 1000000007; 22 long long res = 0; 23 long long d = 26; 24 for (size_t i = 0; i < input.size(); ++i) { 25 long long c = (unsigned char)input[i] - 'a' + 1; 26 res = (res * d + c) % q; 27 } 28 return res; 29 } 30 31 int cmp(string& a, string& d, long long high, long long target) { 32 33 int res = 0; 34 string first = a.substr(0, d.size()); 35 long long hashVal = hashPattern(first); 36 if(hashVal == target) res += 1; 37 38 for(int i = d.size(); i < a.size(); ++i) { 39 hashVal = incremental(hashVal, a[i], a[i-d.size()], high); 40 if(hashVal == target && a.compare(i - d.size() + 1, d.size(), d) == 0) { 41 res += 1; 42 } 43 } 44 return res; 45 46 } 47 48 int main() { 49 string a,b,c,d = ""; 50 51 cin >> a; 52 cin >> b; 53 cin >> c; 54 cin >> d; 55 56 long long q = 1000000007; 57 long long ds = 26; 58 59 long long target = hashPattern(d); 60 61 long long high = 1; 62 63 for (int i = 0; i < d.size() - 1; ++i) { 64 high = high * ds % q; 65 } 66 67 int res = 0; 68 69 if(d.size() <= a.size()) { 70 res += cmp(a,d,high,target); 71 } 72 if(d.size() <= b.size()) { 73 res += cmp(b,d,high, target); 74 } 75 if(d.size() <= c.size()) { 76 res += cmp(c,d,high, target); 77 } 78 79 cout << res << endl; 80 }