Cod sursa(job #1798398)

Utilizator miricelMiricel Daniel Mihai miricel Data 5 noiembrie 2016 10:46:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <string.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[2000002],M[2000002],x;
int i,n,m,k,q;
int urm[2000002],v[2000000];
int main()
{
    f>>N;
    f>>M;
    n=strlen(N);
    m=strlen(M);
    for(i=2; i<=n; i++)
    {
        while(k>0&&N[i-1]!=N[k])
            k=urm[k];
        if(N[i-1]==N[k])
            k++;
        urm[i]=k;
    }
    k=0;
    for(i=0; i<m; i++)
    {
        while(q>0&&M[i]!=N[q])
            q=urm[q];
        if(M[i]==N[q])
            q++;
        if(q==n)
        {
            k++;
            v[k]=i-n+1;
        }
    }
    g<<k<<'\n';
    for(i=1; i<=min(k,1000); i++)
        g<<v[i]<<" ";

    return 0;