Cod sursa(job #3370249)

Utilizator informatica1210Alexia Petre informatica1210 Data 24 octombrie 2026 18:50:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
vector <int> prefix (string a)
{
    int n,x,y;
    vector<int> pi;
    n=a.size();
    pi.push_back(0);
    for (x=1;x<n;x++)
    {
        y=pi[x-1];
        while (y>0 && a[y]!=a[x])
            y=pi[y-1];
        if (a[y]==a[x]) y++;
        pi.push_back(y);
    }
    return pi;
}
vector <int> v;
int main ()
{
    int n1,n2,x,y,nr;
    string a,b;
    f>>a>>b;
    vector<int> pi=prefix(a);
    n1=a.size();
    n2=b.size();
    y=0;nr=0;
    for (x=0;x<n2;x++)
    {
        while (y>0 && b[x]!=a[y])
            y=pi[y-1];
        if (b[x]==a[y]) y++;
        if (y==n1)
        {
            nr++;
            if (nr<=1000) v.push_back(x-n1+1);
            y=pi[y-1];
        }
    }
    g<<nr<<endl;
    for (auto x:v)
        g<<x<<" ";
    f.close ();
    g.close ();
    return 0;
}