Cod sursa(job #1495635)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 3 octombrie 2015 12:46:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>
#define N 2000099
char a[N+1],b[N+1];
int sol[1009],pi[N+1];
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",a+1,b+1);
    int n=strlen(a+1),m=strlen(b+1);
    int k=0,i;
    for(i=2;i<=n;i++){
        while(k!=0&&a[i]!=a[k+1])
            k=pi[k];
        if(a[i]==a[k+1])
            k++;
        pi[i]=k;
        //printf("%d ",pi[i]);
    }
    int nr=0;
    k=0;
    for(i=1;i<=m;i++){
        while(k!=0&&b[i]!=a[k+1])
            k=pi[k];
        if(b[i]==a[k+1])
            k++;
        if(k==n&&nr<1000)
            sol[nr++]=i-n;
    }
    printf("%d\n",nr);
    if(nr>1000)
        for(i=0;i<1000;i++)
            printf("%d ",sol[i]);
    else
        for(i=0;i<nr;i++)
            printf("%d ",sol[i]);
    return 0;
}