Cod sursa(job #714438)

Utilizator mottyMatei-Dan Epure motty Data 15 martie 2012 19:10:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int N = 2000005;

int prefix[N];

string pattern;
string text;

vector <int> finds;

void readCookies()
{
    string auxPat;
    string auxText;

    in >> auxPat >> auxText;

    pattern = ' ';
    pattern += auxPat;

    text = ' ';
    text += auxText;
}

void getCookiePrefixes()
{
    int p = 0;
    prefix[1] = 0;

    for (int i = 2; i < pattern.size(); ++i) {
        while (p && pattern[p + 1] != pattern[i])
            p = prefix[p];
        if (pattern[p + 1] == pattern[i])
            ++p;
        prefix[i] = p;
    }
}

void findCookies()
{
    int p = 0;

    for (int i = 1; i < text.size(); ++i) {
        while (p && pattern[p + 1] != text[i])
            p = prefix[p];
        if (pattern[p + 1] == text[i])
            ++p;
        if (p == pattern.size() - 1) {
            finds.push_back(i + 1 - p);
            p = prefix[p];
        }
    }
}

void printCookies()
{
    out << finds.size() << "\n";

    for (int i = 0; i < 1000 && i < finds.size(); ++i)
        out << finds[i] - 1 << " ";
}

int main()
{
    readCookies();

    getCookiePrefixes();
    findCookies();
    printCookies();

    return 0;
}