Cod sursa(job #2921376)

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

using namespace std;

const int NMAX=100;

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

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

string a,b;

int m,n,i;

int z[NMAX];

int ans;
vector<int> poz;

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]=min(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;
}