Cod sursa(job #2721774)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 12 martie 2021 11:04:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 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 = 2000005;
string a, b;
int pi[nmax];

int main(){
    fin >> a >> b;
    int n = a.size(), m = b.size();
    int l = 0;
    for (int i = 1; i < n; ++i){
        while (l > 0 && a[l] != a[i]){
            l = pi[l - 1];
        }
        if (a[l] == a[i]) ++l;
        pi[i] = l;
    }
    l = 0;
    vector <int> ans;
    int z = 0;
    for (int i = 0; i < m; ++i){
        while (l > 0 && a[l] != b[i]){
            l = pi[l - 1];
        }
        if (a[l] == b[i]) ++l;
        if (l == n){
            l = pi[n - 1];
            if (ans.size() < 1000){
                ans.push_back(i - n + 1);
            }
            ++z;
        }
    }
    fout << z << "\n";
    for (auto it : ans){
        fout << it << " ";
    }
    fin.close();
    fout.close();
    return 0;
}