Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int SIZE = 1000007;
- char text[SIZE], pattern[SIZE];
- int textSize, patternSize;
- int prefix[SIZE];
- void buildPrefix() {
- prefix[1] = 0;
- for (int i = 2; i <= patternSize; i++) {
- int currentPrefix = prefix[i - 1];
- while (currentPrefix > 0 && pattern[currentPrefix + 1] != pattern[i]) {
- currentPrefix = prefix[currentPrefix];
- }
- if (pattern[currentPrefix + 1] == pattern[i]) {
- ++currentPrefix;
- }
- prefix[i] = currentPrefix;
- }
- }
- int countMatches() {
- int matched = 0, ans = 0;
- for (int i = 1; i <= textSize; i++) {
- while (matched > 0 && pattern[matched + 1] != text[i]) {
- matched = prefix[matched];
- }
- if (pattern[matched + 1] == text[i]) {
- ++matched;
- if (matched == patternSize) {
- ++ans;
- matched = prefix[matched];
- }
- }
- }
- return ans;
- }
- int main() {
- cin >> (pattern + 1);
- patternSize = strlen(pattern + 1);
- cin >> (text + 1);
- textSize = strlen(text + 1);
- buildPrefix();
- cout << countMatches() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement