Cod sursa(job #3244780)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 26 septembrie 2024 16:00:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>
#define NMAX 2000009
using namespace std;
ifstream  fin("strmatch.in");
ofstream fout("strmatch.out");
int nr,n,m,urm[NMAX],v[1009];
char A[NMAX],B[NMAX];

void prefix(char ch[])
{
    int i,k=0;
    urm[0]=0;

    for(i=1; i<n; i++)
    {
        while(k>0 && ch[k]!=ch[i])
        {
            k=urm[k-1];
        }

        if(ch[k]==ch[i])
        {
            k++;
            urm[i]=k;
        }
    }
}

int main()
{
    int i,k=0;

    fin.getline(A,NMAX);
    fin.getline(B,NMAX);
    n=strlen(A);
    m=strlen(B);

    if(n>m)
    {
        fout<< 0;
        return 0;
    }

    prefix(A);

    nr=0;
    for(i=0; i<m; i++)
    {
        while(k>0 && A[k]!=B[i])
        {
            k=urm[k-1];
        }

        if(A[k]==B[i])
        {
            k++;
        }

        if(k==n)
        {
            nr++;
            if(nr<=1000)
            {
                v[nr]=i-n+1;
            }
            k=urm[k-1];
        }
    }

    fout<< nr << "\n";

    for(i=1; i<=nr && i<=1000; i++)
    {
        fout<< v[i] << " ";
    }

    return 0;
}