Cod sursa(job #1346295)

Utilizator rockerboyHutter Vince rockerboy Data 18 februarie 2015 09:51:08
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>

std::ifstream in ("strmatch.in");
std::ofstream out("strmatch.out");

std::string a, b;
std::vector<int> p, result;
unsigned i, j, last;

int main()
{
    std::getline (in, a);
    std::getline (in, b);

    p.resize (a.length());
    p[0] = 0;
    last = 0;
    for (i=1; i<p.size(); i++) {
        while (last != 0 && a[last] != a[i]) last = p[last-1];
        if (a[last] == a[i]) last++;
        p[i] = last;
    }

   // for (i=0; i<p.size(); i++) out << p[i];

    j = 0;
    for (i=0; i<b.length(); i++) {
        if (b[i] == a[j]) j++;
        else while (j && b[i] != a[j]) j = p[j-1];

        if (j == a.length()) {
            result.push_back (i-a.length()+1);
            j = p[j-1];
        }
    }
    if (j == a.length()) result.push_back (i-a.length()+1);

    out << result.size() << "\n";
    int l = result.size(); if (l >= 1000) l = 999;
    for (i=0; i<result.size(); i++) out << result[i] << " ";
}