Cod sursa(job #2432954)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 25 iunie 2019 16:00:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

void pi_table(vector<int> &pi, string &A) {
    int k = 0;
    pi.resize(A.size());
    pi[0] = 0;
    for (int i = 1; i < A.size(); ++i) {
        while (k && A[k] != A[i]) {
            k = pi[k - 1];
        }
        if (A[k] == A[i]) {
            ++k;
        }
        pi[i] = k;
    }
}

vector<int> match(vector<int> &pi, string &A, string &B, int &N) {
    int k = 0;
    vector<int> position;
    for (int i = 0; i < B.size(); ++i) {
        while (k && A[k] != B[i]) {
            k = pi[k - 1];
        }
        if (A[k] == B[i]) {
            ++k;
        }
        if (k == A.size() && ++N <= 1000) {
            position.push_back(i - A.size() + 1);
        }
    }
    return position;
}

int main() {
    string A, B;
    int N = 0;
    ofstream fout("strmatch.out");
    ifstream fin("strmatch.in");

    fin >> A >> B;
    vector<int> pi;
    pi_table(pi, A);
    vector<int> position = match(pi, A, B, N);

    fout << N << "\n";

    for (unsigned int i = 0; i < position.size(); ++i) {
        fout << position[i] << " ";
    }

    fout.close();
    fin.close();

    return 0;
}