Cod sursa(job #2989117)

Utilizator andreibrosPeta Andrei Mathias andreibros Data 5 martie 2023 22:45:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX=2000009;
char stra[NMAX],strb[NMAX];
int aparitii[1005],prefix[NMAX];
void build_prefix(int n)
{
    prefix[1]=0;
    int len=0;
    for(int i=2; i<=n; i++)
    {
        while(len>0 && stra[i]!=stra[len+1])
            len=prefix[len];
        if(stra[i]==stra[len+1])
            len++;
        prefix[i]=len;
    }


}
void KMP(int a, int b)
{
    int len=0;
    int k=0;
    for(int i=1; i<=b; i++)
    {

        while(len>0 &&stra[len+1]!=strb[i])
            len=prefix[len];

        if(stra[len+1]==strb[i])
            len++;




        if(len==a)
        {

            k++;
            if(k<=1000)
                aparitii[k]=i-a;
            len=prefix[len];
        }
    }
    out<<k<<'\n';
    for(int i=1; i<=min(1000,k); i++)
    {
        out<<aparitii[i]<<" ";
    }
}
int main()
{
    in.getline(stra,NMAX);
    in.getline(strb,NMAX);
    int lenghta=strlen(stra);
    int lenghtb=strlen(strb);
    for(int i=lenghtb; i>=1; i--)
        strb[i]=strb[i-1];
    for(int i=lenghta; i>=1; i--)
        stra[i]=stra[i-1];
    build_prefix(lenghta);
    KMP(lenghta,lenghtb);

    return 0;
}