Cod sursa(job #1649443)

Utilizator andi12Draghici Andrei andi12 Data 11 martie 2016 13:40:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>

using namespace std;
const int N=2000005;
char a[N],b[N];
int pi[N],poz[N];
int nra,nrb;
void prelucrare()
{
    int k=0,i;
    pi[1]=0;
    for(i=2;i<=nra;i++)
    {
        while(k!=0 && a[k+1]!=a[i])
            k=pi[k];
        if(a[i]==a[k+1])
            k++;
        pi[i]=k;
    }
}
int main()
{
    FILE *in,*out;
    in=fopen("strmatch.in","r");
    out=fopen("strmatch.out","w");
    int i,k=0,nr=0;
    fgets(a,N-1,in);
    fgets(b,N-1,in);
    for(i=0;a[i]!='\n';i++)
        nra++;
    for(i=0;b[i]!='\n';i++)
        nrb++;
    for(i=nra;i>=1;i--)
        a[i]=a[i-1];
    for(i=nrb;i>=1;i--)
        b[i]=b[i-1];
    prelucrare();
    for(i=1;i<=nrb;i++)
    {
        while(k!=0 && b[i]!=a[k+1])
            k=pi[k];
        if(b[i]==a[k+1])
            k++;
        if(k==nra)
        {
            nr++;
            //k=pi[nra];
            if(nr<=1000)
                poz[nr]=i-nra;
        }
    }
    fprintf(out,"%d\n",nr);
    if(nr!=0)
        for(i=1;i<=nr;i++)
            fprintf(out,"%d ",poz[i]);
    return 0;
}