Cod sursa(job #3141678)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 15 iulie 2023 14:47:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int nr,n,m,sol[1001],l,i,p[2000001];
char a[2000004],b[2000004],A[2000004],B[2000004];
int main()
{
    fin>>A>>B;
    strcpy (a+1,A);
    strcpy (b+1,B);
    n=strlen (a+1);
    m=strlen (b+1);
    p[1]=0;
    l=0;
    for (i=2; i<=n; i++)
    {
        while (l>0&&a[l+1]!=a[i])
            l=p[l];
        if (a[l+1]==a[i])
            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-n;
            l=p[l];
        }
    }
    fout<<nr<<"\n";
    for (i=1; i<=min (1000,nr); i++)
        fout<<sol[i]<<" ";
    return 0;
}