Cod sursa(job #803798)

Utilizator mihai995mihai995 mihai995 Data 28 octombrie 2012 12:11:57
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 2000005;
char pattern[N], text[N];
int Z[N], match[N];

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

void strmatch(){
    int best = 0;

    for (int i = 2 ; pattern[i] ; i++){
        if (i <= best + Z[best])
            Z[i] = min(best + Z[best] - i, Z[2 * best - i]);

        while (pattern[i + Z[i]] == pattern[Z[i] + 1])
            ++Z[i];

        if (best + Z[best] < i + Z[i])
            best = i;
    }

    best = 0;

    for (int i = 1 ; text[i] ; i++){
        if (i <= best + match[best])
            match[i] = min(best + match[best] - i, Z[i - best + 1]);

        while (text[i + match[i]] == pattern[match[i] + 1])
            ++match[i];

        if (best + match[best] < i + match[i])
            best = i;
    }
}

int main(){
    vector<int> v;

    in >> pattern + 1 >> text + 1;

    strmatch();

    int Q = strlen(pattern + 1);

    for (int i = 1 ; text[i] ; i++)
        if (match[i] >= Q)
            v.push_back(i);

    out << v.size() << "\n";

    if (v.size() > 1000)
        v.resize(1000);

    for (vector<int> :: iterator it = v.begin() ; it != v.end() ; it++)
        out << (*it) - 1 << " ";

    out << "\n";

    return 0;
}