Cod sursa(job #2266739)

Utilizator zhm248Mustatea Radu zhm248 Data 22 octombrie 2018 21:07:50
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2000010],p[4000010];
int z[4000010],ap[1001];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(p);
    int np=strlen(p),nrap=0;
    gets(s);
    p[strlen(p)]='#';
    strcat(p,s);
    int n=strlen(p);
    int l=0,r=0,i;
    for(i=1;i<n;++i)
    {
        if(i<=r)
            z[i]=min(z[i-l],r-i+1);
        while(i+z[i]<n&&p[i+z[i]]==p[z[i]])
        {
            z[i]++;
        }
        if(i+z[i]-1>=r)
        {
            r=i+z[i]-1;
            l=i;
        }
        if(z[i]==np)
        {
            nrap++;
            if(nrap<=1000)
                ap[nrap]=i-np-1;
        }
    }
    printf("%d\n",nrap);
    for(i=1;i<=nrap&&i<=1000;++i)
    {
        printf("%d ",ap[i]);
    }
    return 0;
}