Cod sursa(job #1891947)

Utilizator dan.marculetFII MarculetDan dan.marculet Data 24 februarie 2017 14:36:28
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <cstring>
#include <vector>

#define MAX_STR 2000005
using namespace std;

auto fin = fopen("strmatch.in", "r");
auto fout = fopen("strmatch.out", "w");

char a[MAX_STR], b[MAX_STR];
unsigned int lena, lenb;
vector<int> matches;

void input() {
    fscanf(fin, "%s", a);
    fscanf(fin, "%s", b);
    lena = strlen(a);
    lenb = strlen(b);
}

void output() {
    fprintf(fout, "%d\n", matches.size());
    for (auto match: matches)
        fprintf(fout, "%d ", match);
}

vector<int> getPrefix(const char* s, unsigned int lens) {
    vector<int> res;
    res.reserve(lens + 1);
    res.push_back(-1);
    auto k = -1;
    for (auto i = 1u; i <= lens; ++i) {
        while (k != -1 && s[k] != s[i - 1])
            k = res[k];
        k += 1;
        res.push_back(k);
    }
    return res;
}

void solve() {
    auto pref = getPrefix(a, lena);
    auto k = 0, i = 0;
    while (i <= lenb - lena) {
        if (k == lena) {
            matches.push_back(i);
            i += k - pref[k];
            k = max(pref[k], 0);
        }
        if (a[k] == b[i + k])
            ++k;
        else {
            i += k - pref[k];
            k = max(pref[k], 0);
        }
    }
}

int main() {
    input();
    solve();
    output();
    return 0;
}