Cod sursa(job #1522699)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 11 noiembrie 2015 21:59:34
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

vector < int > get_pi(string const &W, string const &S) {
    vector < int > pi(W.size());
    int i, q;
    pi[0] = (S[0] == W[0]);
    for(i = 1; i < S.size(); i++) {
        for(q = pi[i-1]; q > 1 && W[q] != S[i]; q = pi[q-1]);
        if(W[q] == S[i]) q++;
        pi[i] = q;
    }
    return pi;
}

int main() {
    int i;
    string S, W;
    vector < int > matches;

    in >> W >> S;

    W += '0';
    vector < int > pi = get_pi(W, S);
    for(i = 0; i < S.size(); i++) {
        if(pi[i] == W.size() - 1) {
            if(matches.size() < 1000) {
                matches.push_back(i - W.size() + 1);
            }
        }
    }

    out << matches.size() << '\n';
    for(auto it : matches) out << it + 1 << ' ';

    return 0;
}