Cod sursa(job #2738366)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 5 aprilie 2021 19:09:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=2e6+5;

char A[NMAX],B[NMAX];
int m,n,p[NMAX],sol[1005],nr;

void prefix()
{
    int k=0;
    p[1]=0;
    for(int i=2;i<=m;i++)
    {
        while(k>0&&A[i]!=A[k+1])
        {
            k=p[k];
        }
        if(A[i]==A[k+1])
        {
            k++;
        }
        p[i]=k;
    }
}
void KMP()
{
    int k=0;
    for(int i=1;i<=n;i++)
    {
        while(k>0&&B[i]!=A[k+1])
        {
            k=p[k];
        }
        if(B[i]==A[k+1])
        {
            k++;
        }
        if(k==m)
        {
            nr++;
            if(nr<=1000)
            {
                sol[nr]=i-m;
            }
            k=p[k];
        }
    }

}

int main()
{
    fin.getline(A+1,NMAX);
    m=fin.gcount()-1;
    fin.getline(B+1,NMAX);
    n=fin.gcount()-1;
    prefix();
    KMP();
    fout<<nr<<'\n';
    if(nr>=1000)nr=1000;
    for(int i=1;i<=nr;i++)
    {
        fout<<sol[i]<<' ';
    }
    return 0;
}