fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long computeHash(int left, int right, const vector<long long> &hashes, const vector<long long> &powers, long long base) {
  5.     return hashes[right] - hashes[left - 1] * powers[right - left + 1];
  6. }
  7.  
  8. bool isMatchingFrequency(const vector<int> &freqS, const vector<int> &freqT) {
  9.     for (int i = 0; i < 26; i++) {
  10.         if (freqS[i] != freqT[i]) return false;
  11.     }
  12.     return true;
  13. }
  14.  
  15. int main() {
  16.     string s, t;
  17.     cin >> s >> t;
  18.  
  19.     int lenS = s.length();
  20.     int lenT = t.length();
  21.     const long long base = 131;
  22.     vector<int> freqS(26, 0);
  23.     vector<int> freqT(26, 0);
  24.     for (char ch : s) {
  25.         freqS[ch - 'a']++;
  26.     }
  27.     vector<long long> hashes(lenT + 1, 0);
  28.     vector<long long> powers(lenT + 1, 1);
  29.     for (int i = 1; i <= lenT; i++) {
  30.         hashes[i] = hashes[i - 1] * base + t[i - 1];
  31.         powers[i] = powers[i - 1] * base;
  32.     }
  33.     set<long long> uniqueHashes;
  34.     for (int i = 0; i < lenT; i++) {
  35.         freqT[t[i] - 'a']++; 
  36.         if (i >= lenS) {
  37.             freqT[t[i - lenS] - 'a']--;
  38.         }
  39.         if (i >= lenS - 1 && isMatchingFrequency(freqS, freqT)) {
  40.             int windowStart = i - lenS + 1;
  41.             int windowEnd = i + 1; 
  42.             uniqueHashes.insert(computeHash(windowStart + 1, windowEnd, hashes, powers, base));
  43.         }
  44.     }
  45.     cout << uniqueHashes.size() << endl;
  46.  
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
aab
abacabaa
stdout
copy 
2
https://ideone.com/gNR4Hf
language:
C++14 (clang 8.0)
created:
26 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!