Cod sursa(job #1404498)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 martie 2015 12:07:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <iostream>
#include <vector>

const int MAX_SIZE(2000001);

int Border [MAX_SIZE], Match;
char a [MAX_SIZE], b [MAX_SIZE];
std::vector<int> v;

inline void Read (void)
{
    std::ifstream input("strmatch.in");
    input >> a >> b;
    input.close();
}

inline void Print (void)
{
    std::ofstream output("strmatch.out");
    output << Match << '\n';
    for (unsigned int i(0) ; i < v.size() ; ++i)
        output << v[i] << ' ';
    output.put('\n');
    output.close();
}

inline void KMP (void)
{
    Border[0] = -1;
    int i(0), j(-1);
    while (a[i])
    {
        while (j >= 0 && a[i] != a[j])
            j = Border[j];
        ++i;
        ++j;
        Border[i] = j;
    }
    i = j = 0;
    while (b[i])
    {
        while (j >= 0 && b[i] != a[j])
            j = Border[j];
        ++i;
        ++j;
        if (!a[j])
        {
            ++Match;
            if (Match <= 1000)
                v.push_back(i - j);
            j = Border[j];
        }
    }
}

int main (void)
{
    Read();
    KMP();
    Print();
    return 0;
}