Cod sursa(job #2899819)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 9 mai 2022 09:50:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

int nr;
vector<int> ans;
int n,m,i,j;

string a,b;

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

int l,r;

int z[2000007];
int mymin(int a, int b)
{
    return (a < b ? a : b);
}
void solve()
{
    fin>>a>>b;
    n=a.length();
    m=b.length();
    int st = n + 2;
    int lg=n;
    a="%"+a+"#"+b;
    n+=m+1;
    for(i=2;i<=n;i++)
    {
        if(i<=r)
            z[i]=mymin(r-i+1,z[i-l+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=1;i<=n;i++)
        cout<<a[i];
    cout<<'\n';
    for(i=1;i<=n;i++)
        cout<<z[i]<<' ';
    cout<<'\n';*/
    for(i=st;i<=n;i++)
        if(z[i]==lg)
        {
            nr++;
            if(nr==1001)
            {
                nr=1000;
                break;
            }
            ans.push_back(i-st);
        }
    fout<<nr<<'\n';
    for(auto it:ans)
        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;
}