Cod sursa(job #1092714)

Utilizator TeOOOVoina Teodora TeOOO Data 27 ianuarie 2014 12:46:49
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
//Include
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

FILE *in, *out;

//Constante
const int sz = (int)2e6+1;

//Functii
void failure_function();

//Variabile
char str[sz], sub[sz];
int strLen, subLen, answer;
int prefix[sz];
char answers[sz];

//Main
int main()
{
	in = fopen("strmatch.in", "rt");
	out = fopen("strmatch.out", "wt");
    fscanf(in,"%s%s",sub+1, str+1);
    strLen = strlen(str+1);
    subLen = strlen(sub+1);

    failure_function();

    int currentPrefix = 0;
    for(int i=1; i<=strLen; ++i)
    {
        while(currentPrefix && sub[currentPrefix+1] != str[i])
            currentPrefix = prefix[currentPrefix];

        if(sub[currentPrefix+1] == str[i])
            ++currentPrefix;

        if(currentPrefix == subLen)
        {
            if(++answer <= 1000)
                answers[answer] = i - subLen;

            currentPrefix = prefix[currentPrefix];
        }
    }

    fprintf(out, "%d\n", answer);
    int limit = min(answer, 1000);
    for(int i=1; i<=limit; ++i)
        fprintf(out,"%d ", answers[i]);

	fclose(in);
	fclose(out);
	return 0;
}

void failure_function()
{
    int currentPrefix = 0;

    for(int i=2; i<=subLen; ++i)
    {
        while(currentPrefix && sub[currentPrefix+1] != sub[i])
            currentPrefix = prefix[currentPrefix];

        if(sub[currentPrefix+1] == sub[i])
            ++currentPrefix;

        prefix[i] = currentPrefix;
    }
}