Cod sursa(job #2376940)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 8 martie 2019 19:18:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#define pb push_back

using namespace std;

const int MAXSIZE = 2e6, MAXN = 1e3;

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

int lengths[MAXSIZE + 10], solutions[MAXN + 10], solutionsNr, n, m;
char prefix[MAXSIZE + 10], str[MAXSIZE + 10];

void read() {
    fin.get(prefix, MAXSIZE +  10);
    fin.get();
    fin.get(str, MAXSIZE +  10);
    m = strlen(prefix);
    n = strlen(str);
}

void preprocess() {
    for (int i = 1, j = 0; i < m;) {
        if (prefix[i] == prefix[j])
            lengths[i++] = ++j;
        else if (!j)
            i++;
        else
            j = lengths[j - 1];
    }
}

void solve() {
    for (int i = 0, j = 0; i < n;) {
        if (str[i] == prefix[j]) {
            i++, j++;
            if (j == m) {
                solutionsNr++;
                if (solutionsNr <= MAXN)
                    solutions[solutionsNr] = i - j;
                j = lengths[j - 1];
            }
        }
        else if (!j)
            i++;
        else
            j = lengths[j - 1];
    }
}

void print() {
    fout << solutionsNr << "\n";
    for (int i = 1; i <= min(solutionsNr, MAXN); ++i)
        fout << solutions[i] << " ";
}

int main() {
    read();
    preprocess();
    solve();
    print();
    return 0;
}