Cod sursa(job #3348440)

Utilizator altomMirel Fanel altom Data 21 martie 2026 22:58:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX=4e6+5;
string a, b;
int kmp[NMAX];
vector<int> sol;

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

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

    int j=0;
    for(int i=0;i<b.size();i++){
        while(j>0 && a[j]!=b[i]){
            j=kmp[j-1];
        }
        if(a[j]==b[i])
            j++;
        if(j==a.size()){
            sol.push_back(i-a.size()+1);
            j=kmp[j-1];
        }
    }

    fout<<sol.size()<<'\n';
    for(int i=0;i<min(int(sol.size()), 1000);i++){
        fout<<sol[i]<<" ";
    }



    return 0;
}