Cod sursa(job #1795013)

Utilizator FlowstaticBejan Irina Flowstatic Data 1 noiembrie 2016 21:45:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>
#define minim(a,b) ((a < b) ? a : b)
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define NMAX 2000100
using namespace std;

char a[NMAX],b[NMAX];
int M,N;
int pi[NMAX],pos[1010];

void Prefix();
void Potrivire();

int nr;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int main()
{
    fin>>a>>b;
    M = strlen(a);
    N = strlen(b);
    for(int i = M; i; --i)
        a[i] = a[i-1];
    for(int i = N; i; --i)
        b[i] = b[i-1];
    a[0]=b[0] = ' ';
    Prefix();
    Potrivire();

    fout<<nr<<'\n';
    FOR(i,1,minim(nr,1000))
        fout<<pos[i]<<" ";
    fout<<'\n';
    return 0;
}

void Prefix()
{
    int q = 0;
    pi[1] = 0;
    FOR(i,2,M)
    {
        while(q && a[q+1] != a[i])
            q = pi[q];
        if(a[q+1] == a[i])
            ++q;
        pi[i] = q;
    }
}

void Potrivire()
{
    int q = 0;
    FOR(i,1,N)
    {
        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;
        }
    }
}