Cod sursa(job #2346913)

Utilizator RaresLiscanLiscan Rares RaresLiscan Data 18 februarie 2019 11:21:24
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 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);
    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);
    }
    v.push_back(0);
}

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) 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 < n; i ++) fout << pot[i] << " ";
    return 0;
}