Cod sursa(job #1896689)

Utilizator BlueCodeMihalache Catalin Alexandru BlueCode Data 28 februarie 2017 20:38:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m, n;
char a[NMax],b[NMax];
int pi[NMax],pos[1010];
inline int minim(int x,int y)
{
    if(x>y)return y;
     else return x;
}
void make_prefix()
{
    int i,q=0;
    pi[1]=0;
    for (i=2;i<=m;++i)
    {
        while (q&&a[q+1]!=a[i])q=pi[q];
        if (a[q+1]==a[i])++q;
        pi[i]=q;
    }
}

int main()
{
    int i,q=0,nr=0;
    f>>a;m=strlen(a);
    f>>b;n=strlen(b);
    for (i=m;i;--i) a[i]=a[i-1];a[0]=' ';
    for (i=n;i;--i) b[i]=b[i-1];b[0]=' ';
    make_prefix();
    for (i=1;i<=n;++i)
    {
        while(q&&a[q+1]!=b[i])q=pi[q];
        if(a[q+1]==b[i])++q;
        if(q==m)
        {q=pi[m];
         ++nr;
        if (nr<=1000)pos[nr]=i-m;
        }
    }

     g<<nr<<'\n';
    for (i=1;i<=minim(nr,1000);++i)
        g<<pos[i]<<" ";


    return 0;
}