Cod sursa(job #2065499)

Utilizator alexandruilieAlex Ilie alexandruilie Data 13 noiembrie 2017 20:36:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <string.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int pref[2000003],lg1,lg2,i,j,nr,v[1001],k;
int main()
{
    f>>a>>b;
    lg1=strlen(a);
    lg2=strlen(b);
    pref[0]=0;
    j=0;
    for(i=1;i<lg1;i++)
    {
        while(j&&a[j]!=a[i]) j=pref[j];
        if(a[j]==a[i]) j++;
        pref[i+1]=j;
    }
    j=0;
    for(i=0;i<lg2;i++)
    {
        while(j&&a[j]!=b[i]) j=pref[j];
        if(a[j]==b[i]) j++;
        if(j==lg1)
        {
            nr++;
            if(k<1000) v[++k]=i-lg1+1;
        }
    }
    g<<nr<<'\n';
    for(i=1;i<=k;i++) g<<v[i]<<' ';
    return 0;
}