Cod sursa(job #1772040)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 6 octombrie 2016 14:25:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
int p[2000100],d[2000100],k,i,m,n,nr;
char a[2000100],b[2000100];
int main()
{
    ifstream f("strmatch.in");
    f>>(a+1)>>(b+1);
    f.close();
    n=strlen(a+1);m=strlen(b+1);
    k=0;p[1]=0;
    for(i=2;i<=n;++i)
    {
        while(k>0&&a[k+1]!=a[i])k=p[k];
        if(a[k+1]==a[i])++k;
        p[i]=k;
    }
    k=0;nr=0;
    for(i=1;i<=m;++i)
    {
        while(k>0&&a[k+1]!=b[i])k=p[k];
        if(a[k+1]==b[i])++k;
        d[i]=k;
        if(k==n)++nr;
    }
    ofstream g("strmatch.out");g<<nr<<'\n';
    for(i=1;i<=m;++i)
        if(d[i]==n)
    {
        nr=i-n;g<<nr<<" ";
    }
    return 0;
}