Cod sursa(job #1613226)

Utilizator PhilipDumitruPhilip Dumitru PhilipDumitru Data 25 februarie 2016 11:39:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>
#include <queue>

using namespace std;

char A[2000002];
char B[2000002];
int automat[2000002];
int a, b; //no need to know length for b though
queue<int> res;

void buildKMP(char *str)
{
    int k = 0;
    automat[1] = 0;
    int it;
    for (it = 2; str[it] != '\n'; ++it)
    {
        while (k > 0 && str[it] != str[k+1])
            k = automat[k];
        if (str[k+1] == str[it])
            ++k;
        automat[it] = k;
    }
    a = it - 1;
}
void searchStr(char* str, char* Sstr)
{
    int k = 0;
    int it;
    for (it = 1; str[it] != '\n'; ++it)
    {
        while (k > 0 && str[it] != Sstr[k+1])
            k = automat[k];
        if (Sstr[k+1] == str[it])
            ++k;
        if (k == a)
        {
            if (b++ < 1000)
                res.push(it - a);
        }
    }
}

int main()
{
    FILE * fin = fopen("strmatch.in", "r");
    FILE * fout = fopen("strmatch.out", "w");

    fgets(A+1, 2000001, fin);
    fgets(B+1, 2000001, fin);

    buildKMP(A);
    searchStr(B, A);// search A in B

    fprintf(fout, "%d\n", b);
    while (!res.empty())
    {
        fprintf(fout, "%d ", res.front());
        res.pop();
    }
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}