Cod sursa(job #1814475)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 24 noiembrie 2016 01:07:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMax = 2e6 + 5;

int A[NMax];

int main() {

    ios::sync_with_stdio(false);
    fin.tie(NULL);

    string a, b;
    fin >> a >> b;

    a = '$' + a;
    b = '$' + b;

    A[1] = 0;
    int k = 0;
    for(int i = 2; i <= a.size(); i++) {
        while(k > 0 && a[k + 1] != a[i]) {
            k = A[k];
        }
        if(a[k + 1] == a[i]) {
            k++;
        }
        A[i] = k;
    }

    k = 0;
    int p = 0;
    vector < int > ans;
    for(int i = 1; i <= b.size(); i++) {
        while(k > 0 && b[i] != a[k + 1]) {
            k = A[k];
        }
        if(b[i] == a[k + 1]) {
            k++;
        }
        if(k == a.size() - 1) {
            p++;
            if((int)(ans.size()) < 1000) ans.push_back(i - k);
            k = A[k];
        }
    }

    fout << p << "\n";
    for(auto it: ans) fout << it << " ";

    return 0;
}