Cod sursa(job #1951925)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 3 aprilie 2017 21:07:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 2e6 + 5;

int Pi[NMax];
vector < int > v;

int main() {
    ios::sync_with_stdio(false);

    string a, b;
    fin >> a >> b;
    int n = (int)a.size();
    int m = (int)b.size();

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

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

    int ans = 0;
    k = 0;
    for(int i = 1; i <= m; i++) {
        while(k > 0 && a[k + 1] != b[i]) {
            k = Pi[k];
        }
        if(a[k + 1] == b[i]) k++;
        if(k == n) {
            ans++;
            v.push_back(i - n);
        }
    }

    fout << ans << "\n";
    for(int i = 0; i < min((int)v.size(), 1000); i++) fout << v[i] << " ";
    return 0;
}