Cod sursa(job #1552503)

Utilizator delia_99Delia Draghici delia_99 Data 18 decembrie 2015 10:59:55
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#define NMAX 2000000
#include <algorithm>
#include <cstring>
using namespace std;
char A[NMAX+10],B[NMAX+10];
int n,m,i,phi[NMAX+10],phi2[NMAX+10],sol,k;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(A+1);
    gets(B+1);
    n=strlen(A+1);
    m=strlen(B+1);
    phi[1]=0;
    for(i=2; i<=n; ++i)
    {
        k=phi[i-1];
        while(k && A[i]!=A[k+1])
            k=phi[k];
        if(A[i]==A[k+1])
            phi[i]=k+1;
        else phi[i]=0;
    }
    phi2[1]=0;
    for(i=2; i<=m; ++i)
    {
        k=phi2[i-1];
        while(k && B[i]!=A[k+1])
            k=phi2[k];
        if(B[i]==A[k+1])
            phi2[i]=k+1;
        else phi2[i]=0;
        if(phi2[i]==n)
            ++sol;
    }
    printf("%d\n",sol);
    sol=min(sol,1000);
    for(i=1; i<=m && sol; ++i)
        if(phi2[i]==n)
        {
            printf("%d ",i-n);
            --sol;
        }
    return 0;
}