Cod sursa(job #3291297)

Utilizator Floroiu_MariusFloroiu Marius Cristian Floroiu_Marius Data 3 aprilie 2025 23:59:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int lps[2000003];
vector<int> rez;
int cnt;
int main()
{
    fin>>a>>b;
    int n=b.size(),m=a.size();
    int st=0,dr=1;
    while (dr<m)
    {
        if (a[dr]==a[st])
        {
            st++;
            lps[dr]=st;
            dr++;
        }
        else
        {
            if (st!=0) st=lps[st-1];
            else dr++;
        }
    }
    st=0,dr=0;
    while (dr<n)
    {
        if (b[dr]==a[st])
        {
            dr++;
            st++;
        }
        else
        {
            if (st!=0) st=lps[st-1];
            else dr++;
        }
        if (st==m)
        {
            cnt++;
            if (rez.size()<1000) rez.push_back(dr-m);
            st=lps[st-1];
        }
    }
    fout<<cnt<<'\n';
    for (auto i:rez)
        fout<<i<<" ";
    return 0;
}