Cod sursa(job #3313379)

Utilizator calinarulMarinescu Calin calinarul Data 3 octombrie 2025 22:00:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2*1e6+5;
int pi[NMAX];
string a,b;
vector<int>rez;
void precalculate()
{
    int m=a.length();
    for(int i=1,j=0;i<m;i++)
    {
        while(j>0 && a[j]!=a[i])j=pi[j-1];
        if(a[j]==a[i])j++;
        pi[i]=j;
    }
}
void kmp()
{
    int n=b.length();int m=a.length();if(m==0)return;
    for(int i=0,j=0;i<n;i++)
    {
        while (j>0 && a[j]!=b[i])j=pi[j-1];
        if(a[j]==b[i])j++;
        if(j==m){rez.push_back(i-m+1);j=pi[j-1];}
    }
}
int main()
{
    fin>>a>>b;
    precalculate();
    kmp();
    fout<<rez.size()<<'\n';
    for(int i=0;i<min((int)rez.size(),1000);i++)fout<<rez[i]<<" ";
}