Cod sursa(job #3240152)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 12 august 2024 20:48:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream  fin("strmatch.in");
ofstream fout("strmatch.out");
int i,nr,n,m,urm[2000009],a[2000009];
char A[2000009],B[2000009];

void urmatorul(char *P)
{
    int k=-1,x;
    urm[0]=0;

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

        if(A[k+1]==A[x])
        {
            k++;
        }

        urm[x]=k;
    }
}

int main()
{
    int x=-1;

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

    urmatorul(A);

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

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

        if(x==n-1)
        {
            nr++;
            a[nr]=i-n+1;
            x=urm[x];
        }
    }

    fout<< nr << "\n";

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

    return 0;
}