Cod sursa(job #1051899)

Utilizator vasandANDREI POP vasand Data 10 decembrie 2013 17:50:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
# include <iostream>
# include <fstream>
# include <string.h>
# define nmax 2000000
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char T[nmax], P[nmax];
int n,m,L[nmax],nr,v[nmax];;

int main()
{
    f.getline(P+1,nmax);
    f.getline(T+1,nmax);
    m=strlen(P+1);
    n=strlen(T+1);

    int i,k,p,t;

    L[1]=0;
    for(i=2; i<=m; i++)
    {
        k=L[i-1];
        while(k>0 && P[i]!=P[k+1])
            k=L[k];
        if(P[i]==P[k+1])
            k+=1;
        L[i]=k;
    }

    k=0;
    for(i=1; i<=n; i++)
    {
        while(k>0 && P[k+1]!=T[i])
            k=L[k];
        if(P[k+1]==T[i])
            k=k+1;
        if(k==m)
        {
            v[++nr]=i-k;
            k=L[k];
        }
    }

    g<<nr<<'\n';
    for(i=1; i<=nr; i++)
        g<<v[i]<<" ";

    return 0;
}