Cod sursa(job #1871668)

Utilizator tudoras8tudoras8 tudoras8 Data 7 februarie 2017 16:25:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    
    string pattern, text;
    vector<int> ans;
    
    cin >> pattern >> text;
    
    vector<int> lps(pattern.size());
    int i = 1;
    int j = 0;
    while (i < pattern.size()) {
        if (pattern[i] == pattern[j]) {
            lps[i] = j + 1;
            ++i, ++j;
        } else {
            if (j == 0) {
                lps[i] = 0;
                ++i;
            } else {
                j = lps[j - 1];
            }
        }
    }
    
    i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (text[i] == pattern[j]) {
            ++i, ++j;
        } else {
            if (j == 0) {
                ++i;
            } else {
                j = lps[j - 1];
            }
        }
        if (j == pattern.size()) {
            ans.push_back(i - pattern.size());
            j = lps[j - 1];
        }
    }
    
    cout << ans.size() << '\n';
    for (int x : ans) {
        cout << x << ' ';
    }
    
    return 0;
}