Cod sursa(job #742302)

Utilizator freak93Adrian Budau freak93 Data 29 aprilie 2012 15:04:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> prefix(const string &subject) {
    vector<int> pi(subject.size(), 0);

    // Ignore the first char because from there we match the whole string
    size_t matchTo = 0;
    for (size_t i = 1; i < subject.size(); ++i) {
        while (matchTo > 0 && subject[i] != subject[matchTo])
            matchTo = pi[matchTo - 1];

        if (subject[i] == subject[matchTo])
            ++matchTo;

        pi[i] = matchTo;
    }

    return pi;
}

vector<int> kmp(const string &pattern, const string &subject) {
    vector<int> pi = prefix(pattern);
    vector<int> matches;

    size_t matchTo = 0;
    for (size_t i = 0; i < subject.size(); ++i) {
        while (matchTo > 0 && subject[i] != pattern[matchTo])
            matchTo = pi[matchTo - 1];

        if (subject[i] == pattern[matchTo])
            ++matchTo;

        if (matchTo == pattern.size())
            matches.push_back(i - pattern.size() + 1);
    }

    return matches;
}

int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    string A, B;
    cin >> A >> B;
 
    vector<int> answer = kmp(A, B);
    cout << answer.size() << "\n";
    
    for (int i = 0; i < min(static_cast<int>(answer.size()), 1000); ++i)
        cout << answer[i] << " ";
    cout << "\n";
}