Cod sursa(job #2084281)

Utilizator ianiIani Biro iani Data 8 decembrie 2017 21:29:44
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[2000005],b[2000005];

int l[2000005],poz[2000005];

int main()
{
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    fscanf(fin,"%s\n%s",a,b);
    //cout<<a<<endl<<b;
    int nr=0,m,n;
    m=strlen(a);
    n=strlen(b);
    l[0]=0;
    int i=1,j=0,k=0;
    while(i<m)
        if(a[i]==a[j])
        {
            l[i]=j+1;
            i++;
            j++;
        }
        else if(j==0)
            l[i++]=0;
        else
            j=l[j-1];
    i=j=0;
    while(i<n)
        if(b[i]==a[j])
        {
            i++;
            j++;
            if(j==m)
            {
                nr++;
                poz[k++]=i-m;
                j=l[j-1];
            }
        }
        else if(j==0)
            i++;
        else
            j=l[j-1];
    fprintf(fout,"%d\n",nr);
    for (int i=0; i<k; i++)
        fprintf(fout,"%d ",poz[i]);
    return 0;
}