Cod sursa(job #1976921)

Utilizator taigi100Cazacu Robert taigi100 Data 4 mai 2017 16:02:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 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;
int sol;

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

void ComputePrefix() {
    int len = strlen(pattern+1);
    int k = 0;
    for (int i = 2; 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+1);
    int lenarr = strlen(arr+1);
    int k = 0;
    for (int i = 1; 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) {
            if(Sol.size() < 1000)
                Sol.push_back(i - k);
            ++sol;
        }
    }
}

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

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


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