algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }