Cod sursa(job #1438982)

Utilizator sorin2kSorin Nutu sorin2k Data 21 mai 2015 10:59:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;

string a, b;
// pi[i] the length of the greatest prefix of a(i-1) which is also a suffix for a
int pi[2000001];
vector<int> sol;

void prefix_function() {
    int i, k = 0;
    for (i = 1; i < a.size(); i++) {
        while (k > 0 && a[i] != a[k]) {
            k = pi[k-1];
        }
        if (a[i] == a[k]) {
            k++;
        }
        pi[i] = k;
    }
}

void match() {
    int i, k = 0;
    for (i = 0; i < b.size(); i++) {
        while (k > 0 && b[i] != a[k]) {
            k = pi[k-1];
        }
        if (b[i] == a[k]) {
            k++;
            if (k == a.size()) {
                sol.push_back(i - a.size() + 1);
                k = pi[k-1];
            }
        }
    }
}


int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin >> a >> b;
    prefix_function();
    match();

    fout << sol.size() << "\n";
    for (int i = 0; i < sol.size() && i < 1000; i++) {
        fout << sol[i] << " ";
    }

    return 0;
}