Cod sursa(job #2921379)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 30 august 2022 16:01:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX=2e6+5;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

//char a[NMAX],b[NMAX];

string a,b;

int m,n,i;

int z[2*NMAX];

int ans;
vector<int> poz;

int mymin(int a, int b)
{
    return (a<b?a:b);
}

void solve()
{
    fin>>a>>b;
    m=a.length();
    a="#"+a+"&"+b;
    n=a.length()-1;
    int l=0,r=0;
    for(i=1;i<=n;i++)
    {
        if(i<=r)
            z[i]=mymin(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+1])z[i]++;
        if(i+z[i]-1>r)
        {
            r=i+z[i]-1;
            l=i;
        }
    }
    for(i=m+2;i<=n;i++)
        if(z[i]==m)
        {
            ans++;
            if(ans<=1000)
                poz.push_back(i-m-2);
        }
    fout<<ans<<'\n';
    for(auto it:poz)
        fout<<it<<' ';
    fout<<'\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}