Cod sursa(job #2899823)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 9 mai 2022 10:00:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,lg;

int start;

string a,b;
vector<int> poz;
int ans;

int l,r;

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

int i;
int z[4000005];

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

void solve()
{
    fin>>a>>b;
    m=a.length();
    a="%"+a+"&"+b;
    n=a.length()-1;
    for(i=2;i<=n;i++)
    {
        if(i<=r)
            z[i]=mymin(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&a[z[i]+1]==a[i+z[i]])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<<' ';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tt=1;
    //cin>>tt;
    for(int t=1;t<=tt;t++)
        solve();
    return 0;
}