Cod sursa(job #2266757)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 22 octombrie 2018 21:15:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
char a[2000005], b[2000005], p[4000005];
int z[4000005],l,r,i,n,nr,q;
void zet(char p[4000005])
{
   // n=strlen(p+1);
    z[0]=0;
    l=r=0;
    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;
        }
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&a);
    q=strlen(a);
    scanf("%s",&b);
    int qq=strlen(b);
    n=-1;
    for(i=0;i<q;i++)
    {
        n++;
        p[n]=a[i];
    }
    n++;
    p[n]='#';
    for(i=0;i<qq;i++)
    {
        n++;
        p[n]=b[i];
    }
    p[n+1]=0;
    n++;
    zet(p);
    for(i=q+1;i<=n;i++)
    {
        if(z[i]==q)nr++;
    }
    printf("%d\n",nr);
    int t=0;
    for(i=q+1;i<=n;i++)
    {
        if(z[i]==q){printf("%d ",i-q-1);t++;}
        if(t==1000)break;
    }
    return 0;
}