Cod sursa(job #1655621)

Utilizator Vlad_317Vlad Panait Vlad_317 Data 18 martie 2016 09:40:06
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <string.h>
using namespace std;

const int MAX = 2005;

char a[MAX], b[MAX];
int la, lb;
int pi[MAX], pos[1024];
int nr;

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

int main()
{
    FILE *fin, *fout;

    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");

    fgets(1 + a, MAX, fin);
    fgets(1 + b, MAX, fin);

    la = strlen(a + 1) - 1;
    lb = strlen(b + 1) - 1;

    //fprintf(fout, "%d %d", la, lb);

    prefix();

    int q = 0;

    for(int i = 1; i <= lb; i++)
    {
        while(q && a[q + 1] != b[i])
            q = pi[q];
        if(a[q + 1] == b[i])
            q++;
        if(q == la)
        {
            q = pi[la];
            nr++;
            if(nr <= 1000)
                pos[nr] = i - la;
        }
    }

    fprintf(fout, "%d\n", nr);

    if(nr > 1000)
        nr = 1000;

    for(int i = 1; i <= nr; i++)
        fprintf(fout, "%d ", pos[i]);

    return 0;
}