Cod sursa(job #3359325)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 27 iunie 2026 00:40:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#pragma GCC optimize("Ofast,unroll-loops")
#include<fstream>
#include<string>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int>pi;
void calcPi(string &s){
    pi.resize(s.size()+1);
    pi[1]=0;
    int k=0;
    for(int i=2;i<=s.size();++i){
        while(k != 0 && s[k] != s[i-1]) {
            k = pi[k]; 
        }
        if(s[k] == s[i-1]) {
            k++;
        }
        pi[i] = k;
    }

}

void solve(string &a,string &b){
    vector<int>rez;
    int k=0;
    for(int i = 1; i <= b.size(); i++) {
        while(k != 0 && a[k] != b[i-1]) {
            k = pi[k];
        }
        if(a[k] == b[i-1]) {
            k++;
        }
        if(k == a.size()) {
            rez.push_back(i);
        }
    }
    fout<<rez.size()<<"\n";
    for(auto i:rez){
        fout<<i-a.size()<<" ";
    }

}
int main(){
    string a,b;
    fin>>a>>b;
    calcPi(a);
    solve(a,b);
    return 0;
}