Advertisement
Guest User

Untitled

a guest
Apr 5th, 2020
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int SIZE = 1000007;
  6.  
  7. char text[SIZE], pattern[SIZE];
  8. int textSize, patternSize;
  9. int prefix[SIZE];
  10.  
  11. void buildPrefix() {
  12.   prefix[1] = 0;
  13.  
  14.   for (int i = 2; i <= patternSize; i++) {
  15.     int currentPrefix = prefix[i - 1];
  16.  
  17.     while (currentPrefix > 0 && pattern[currentPrefix + 1] != pattern[i]) {
  18.       currentPrefix = prefix[currentPrefix];
  19.     }
  20.  
  21.     if (pattern[currentPrefix + 1] == pattern[i]) {
  22.       ++currentPrefix;
  23.     }
  24.  
  25.     prefix[i] = currentPrefix;
  26.   }
  27. }
  28.  
  29. int countMatches() {
  30.   int matched = 0, ans = 0;
  31.  
  32.   for (int i = 1; i <= textSize; i++) {
  33.     while (matched > 0 && pattern[matched + 1] != text[i]) {
  34.       matched = prefix[matched];
  35.     }
  36.  
  37.     if (pattern[matched + 1] == text[i]) {
  38.       ++matched;
  39.  
  40.       if (matched == patternSize) {
  41.         ++ans;
  42.         matched = prefix[matched];
  43.       }
  44.     }
  45.   }
  46.  
  47.   return ans;
  48. }
  49.  
  50. int main() {
  51.   cin >> (pattern + 1);
  52.   patternSize = strlen(pattern + 1);
  53.  
  54.   cin >> (text + 1);
  55.   textSize = strlen(text + 1);
  56.  
  57.   buildPrefix();
  58.   cout << countMatches() << endl;
  59.  
  60.   return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement