Cod sursa(job #1921671)

Utilizator gabrielamoldovanMoldovan Gabriela gabrielamoldovan Data 10 martie 2017 13:49:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n, m;
char a[nmax], b[nmax];
int pos[1024], p[nmax];

void prefix()
{
    int i, q=0;
    for(i=2, p[1]=0; i<=n; ++i)
    {
        while(q && a[q+1]!=a[i]) q=p[q];
        if(a[q+1]==a[i]) ++q;
        p[i]=q;
    }
}

int main()
{
    f>>a>>b;
    n=strlen(a);
    m=strlen(b);
    for(int i=n; i; --i) a[i]=a[i-1];
    a[0]=' ';
    for(int i=m; i; --i) b[i]=b[i-1];
    b[0]=' ';
    prefix();
    int q=0, nr=0;
    for(int i=1; i<=m; ++i)
    {
        while(q && a[q+1]!=b[i]) q=p[q];
        if(a[q+1]==b[i]) ++q;
        if(q==n)
        {
            q=p[n];
            ++nr;
            if(nr<=1000)
            {
                pos[nr]=i-n;
            }
        }
    }
    g<<nr<<"\n";
    for(int i=1; i<=min(nr, 1000); ++i)
    {
        g<<pos[i]<<" ";
    }
    return 0;
}