Cod sursa(job #2346975)

Utilizator RaresLiscanLiscan Rares RaresLiscan Data 18 februarie 2019 11:53:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

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

string a, b;
vector <int> v, pot;

void prefix()
{
    int n = a.size(), k = 0;
    v.push_back(0), v.push_back(0);
    for (int i = 2; i < n; i ++) {
        while (k > 0 && a[k + 1] != a[i]) k = v[k];
        if (a[k + 1] == a[i]) k ++;
        v.push_back(k);
    }
}

void potrivire()
{
    int n = a.size(), m = b.size(), q = 0;
    for (int i = 1; i < m; i ++) {
        while (q > 0 && a[q + 1] != b[i]) q = v[q];
        if (a[q + 1] == b[i]) q ++;
        if (q == n-1 && a[0] == b[i - n + 1]) pot.push_back(i - n + 1);
    }
}

int main()
{
    fin >> a >> b;
    prefix();
    potrivire();
    int n = pot.size();
    fout << n << "\n";
    for (int i = 0; i < min(n, 1000); i ++) fout << pot[i] << " ";
    return 0;
}