Cod sursa(job #3241169)

Utilizator Gabriel_DaescuDaescu Gabriel Florin Gabriel_Daescu Data 27 august 2024 12:17:04
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream  fin("strmatch.in");
ofstream fout("strmatch.out");
int i,nr,n,m,urm[20000010],a[1009];
char T[2000010],P[2000010];

void urmatorul(char *P)
{
    int k=0;

    for(int x=2; x<=m; x++)
    {
        while(k && P[k+1]!=P[x])
        {
            k=urm[k];
        }

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

        urm[x]=k;
    }
}

int main()
{
    int x=0;

    fin.get(P,2000009);
    fin.get();
    fin.get(T,2000009);
    n=strlen(T+1);
    m=strlen(P+1);

    urmatorul(P);

    nr=0;
    for(i=1; i<=n; i++)
    {
        while(x && P[x+1]!=T[i])
        {
            x=urm[x];
        }

        if(P[x+1]==T[i])
        {
            x++;
        }

        if(x==m)
        {
            nr++;
            if(nr<=1000)
            {
                a[nr]=i;
            }
            x=urm[x];
        }
    }

    fout<< nr << "\n";

    for(i=1; i<=min(nr,1000); i++)
    {
        fout<< a[i]-m << " ";
    }

    return 0;
}