Cod sursa(job #3141786)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 16 iulie 2023 15:55:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[2000003],b[2000003],A[2000003],B[2000003];
int p[2000003],n,m,sol[1003],i,nr,l;
int main()
{
    cin>>A>>B;
    strcpy(a+1,A);
    strcpy(b+1,B);
    n=strlen(a+1);
    m=strlen(b+1);
    l=0;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        while(l!=0&&a[i]!=a[l+1])
            l=p[l];
        if(a[i]==a[l+1])
            l++;
        p[i]=l;
    }

    l=0;
    for(i=1;i<=m;i++)
    {
        while(l!=0&&b[i]!=a[l+1])
            l=p[l];
        if(b[i]==a[l+1])
            l++;
        if(l==n)
        {
            nr++;
            if(nr<=1000)
                sol[nr]=i-l+1;
            l=p[l];
        }
    }
    cout<<nr<<'\n';
    if(nr>1000)
        nr=1000;
    for(i=1;i<=nr;i++)
        cout<<sol[i]-1<<" ";
    return 0;
}