Cod sursa(job #1976915)

Utilizator taigi100Cazacu Robert taigi100 Data 4 mai 2017 15:46:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
/*
    Keep It Simple!
*/

#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int MAX_N = 2000005;

char arr[MAX_N],pattern[MAX_N];
int prefix_array[MAX_N];
vector<int> Sol;

void ReadInput() {
    ifstream f("strmatch.in");
    f >> pattern;
    f >> arr;
}

void ComputePrefix() {
    int len = strlen(pattern);
    int k = -1;
    for (int i = 1; i < len; ++i) {
        while (k > 0 && pattern[k+1] != pattern[i])
            k = prefix_array[k];
        if (pattern[k+1] == pattern[i]) ++k;
        prefix_array[i] = k;
    }
}

void FindMatch() {
    int lenpat = strlen(pattern);
    int lenarr = strlen(arr);
    int k = -1;
    for (int i = 0; i < lenarr; ++i) {
        while (k > 0 && pattern[k+1] != arr[i])
            k = prefix_array[k];
        if (pattern[k+1] == arr[i])
            ++k;
        if (k == lenpat - 1)
            Sol.push_back(i - k);
    }
}

void PrintSolution() {
    ofstream g("strmatch.out");
    g << Sol.size() << '\n';
    for (auto i : Sol)
        g << i << ' ';
    g << '\n';
}

void Solve() {
    ReadInput();
    ComputePrefix();
    FindMatch();
    PrintSolution();
}


int main()
{
    Solve();
    return 0;
}