Cod sursa(job #2975545)

Utilizator matei8787Matei Dobrea matei8787 Data 6 februarie 2023 19:08:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b, sz;
int z[2000005];
void citire()
{
    in>>a>>b;
}
vector<int> ans;
void rez()
{
    sz = a + '|' + b;
    int l=0, r=0;
    int n = sz.size();
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( i <= r )
        {
            z[i] = min(z[i-l], r - i + 1);
        }
        while (z[i] + i <= n && sz[z[i]] == sz[i+z[i]])
            z[i]++;
        if ( i + z[i] - 1 > r )
        {
            l = i;
            r = i + z[i] - 1;
        }
    }
    for ( int i = a.size() + 1 ; i < n ; i++ )
    {
        if ( z[i] == a.size() )
        {
            ans.push_back(i-a.size()-1);
        }
        if ( ans.size() >= 1000 )
            break;
    }
    out<<ans.size()<<'\n';
    for ( int x : ans )
    {
        out<<x<<" ";
    }
}
int main()
{
    citire();
    rez();
    return 0;
}