Cod sursa(job #1552489)

Utilizator rzvrzvNicolescu Razvan rzvrzv Data 18 decembrie 2015 10:42:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int phi[2000003],phi2[2000003],i,n,m,k,nr,poz[1002];
char s1[2000003],s2[2000003];

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(s1+1);
    gets(s2+1);
    m=strlen(s1+1);
    for(i=2;i<=m;i++)
    {
        k=phi[i-1];
        while(k>0&&s1[i]!=s1[k+1])
        {
            k=phi[k];
        }
        if(s1[i]==s1[k+1])
        {
            phi[i]=k+1;
        }
        else
        {
            phi[i]=0;
        }
    }
    s1[m+1]=' ';
    n=strlen(s2+1);
    for(i=1;i<=n;i++)
    {
        k=phi2[i-1];
        while(k>0&&s2[i]!=s1[k+1])
        {
            k=phi[k];
        }
        if(s2[i]==s1[k+1])
        {
            phi2[i]=k+1;
        }
        else
        {
            phi2[i]=0;
        }
        if(phi2[i]==m)
        {
            nr++;
            if(nr<=1000)
            {
                poz[nr]=i-m;
            }
        }

    }
    printf("%d\n",nr);
    for(i=1;i<=min(nr,1000);i++)
    {
        printf("%d ",poz[i]);
    }
}