Cod sursa(job #311508)

Utilizator sandyxpSanduleac Dan sandyxp Data 3 mai 2009 16:39:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <string>
#include <iterator>
#include <vector>
using namespace std;

#define NUME "strmatch"
ifstream fi(NUME".in");
ofstream fo(NUME".out");
#define MAXN 2000001

string A, B;
int pi[MAXN];

void build(string str) {
    int i;
    pi[0] = -1;
    for (i = 1; i <= str.size(); ++i) {
        pi[i] = pi[i-1] + 1;
        while (pi[i] > 0 && str[i-1] != str[pi[i]-1])
            pi[i] = pi[pi[i] - 1] + 1;
    }
}

int main()
{
    vector<int> occ;
    int i, j;
    fi >> B >> A; // B = pattern
    build(B);
    for (i = 0, j = 0; i < A.size(); ++i) {
        while (j && A[i] != B[j])
            j = pi[j];
        if (A[i] == B[j])
            ++j;
        if (j == B.size()) {
            occ.push_back(i-j+1);
            j = pi[j];
        }
    }
    fo << occ.size() << "\n";
    copy(occ.begin(), occ.end(), ostream_iterator<int>(fo, " "));
    return 0;
}