Cod sursa(job #2717415)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 7 martie 2021 13:11:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;

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

string a, b;
int pref[2000005], nr;
vector<int> ans;

int main() {
    fin >> a >> b;

    for(int i = 1; i < a.length(); i++) {
        pref[i] = pref[i-1];
        while(pref[i] > 0 && a[i] != a[pref[i]])
            pref[i] = pref[pref[i]-1];
        if(a[i] == a[pref[i]])
            pref[i]++;
    }

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

    }
    fout << nr << '\n';
    for(auto x: ans) fout << x << ' ' ;

}