Cod sursa(job #1752180)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 2 septembrie 2016 21:50:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000001],b[2000001],buff[5000000];
int poz[2000001],v[2000001],lung=1,p;
void read(char *z)
{int x=0;
    while((buff[p]<'A'||buff[p]>'z')&&(buff[p]<'0'||buff[p]>'9'))
    {
        if(++p==lung){lung=fread(buff,1,5000000,stdin);p=0; }
    }
    while((buff[p]>='A'&&buff[p]<='z')||(buff[p]>='0'&&buff[p]<='9'))
    {
        *z=buff[p];
        ++z;
        if(++p==lung){lung=fread(buff,1,5000000,stdin);p=0; }
    }*z=0;
}


int main()
{freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int n,m,i,j=0,k;
//scanf("%s%s",&a,&b);
read(a);
read(b);
n=strlen(a);m=strlen(b);
poz[0]=poz[1]=-1;
if(a[0]==a[1])poz[1]=0;

k=0;
for(i=2;i<n;i++)
{
    while(k>-1&&a[i]!=a[k+1])
        k=poz[k];
    if(a[i]==a[k+1])k++;
    poz[i]=k;
}
k=-1;
for(i=0;i<m;i++)
{
    while(k>-1&&b[i]!=a[k+1])
        k=poz[k];
    if(b[i]==a[k+1])k++;
    if(k==n-1)v[j++]=i-k;
}printf("%d\n",j);if(j>1000)j=1000;
for(i=0;i<j;i++)printf("%d ",v[i]);



    return 0;
}