Cod sursa(job #2738455)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 5 aprilie 2021 21:10:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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 l = 0;
    for (int i = 1; i < a.size(); ++i){
        while (l > 0 && a[i] != a[l]){
            l = pi[l - 1];
        }
        if (a[i] == a[l]){
            ++l;
        }
        pi[i] = l;
    }
    l = 0;
    vector <int> ans;
    int z = 0;
    for (int i = 0; i < b.size(); ++i){
        while (l > 0 && b[i] != a[l]){
            l = pi[l - 1];
        }
        if (a[l] == b[i]){
            ++l;
        }
        if (l == a.size()){
            l = pi[a.size() - 1];
            if (ans.size() < 1000){
                ans.push_back(i - a.size() + 1);
            }
            ++z;
        }
    }
    fout << z << "\n";
    for (auto it : ans){
        fout << it << " ";
    }
    fin.close();
    fout.close();
    return 0;
}