Cod sursa(job #1946972)

Utilizator ana-maria.simiAna-Maria Simionescu ana-maria.simi Data 30 martie 2017 17:25:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int Urm[2000010],n,m,sol[1005],nr;
char T[2000010],P[2000010];

void initurm(char *P)
{
    int k=-1, x;
    Urm[0]=0;
    for(x=1; x<m; x++)
    {
        while(k>0 && P[k+1]!=P[x])
            k=Urm[k];
        if(P[k+1]==P[x])
            k++;
        Urm[x]=k;

    }
}

int main()
{int i, x=-1;
f.getline(P,2000010);
f.getline(T,2000010);
n=strlen(T);
m=strlen(P);
initurm(P);
for(i=0; i<n; i++)
{
    while(x>0 && P[x+1]!=T[i])
        x=Urm[x];
    if(P[x+1]==T[i])
        x++;
    if(x==m-1)
        {nr++;
        if(nr<=1000)
            sol[nr]=i-m+1;
        x=Urm[x];}
}

g<<nr<<'\n';
nr=min(nr,1000);
for(i=1; i<=nr; i++)
    g<<sol[i]<<" ";
    return 0;
}