Cod sursa(job #2195312)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 15 aprilie 2018 23:26:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define Nmax 2000005

using namespace std;

char A[Nmax], B[Nmax];
int a, b, prefix[Nmax];
vector <int> solution;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin >> B >> A;

    a = strlen(A);
    b = strlen(B);
    int k = 0;
    for (int i = 1; i < b; i++) {
        while (k && B[k] != B[i])
            k = prefix[k - 1];
        if (B[k] == B[i])
            k++;
        prefix[i] = k;
    }

    k = 0;
    for (int i = 0; i < a; i++) {
        while (k && B[k] != A[i])
            k = prefix[k - 1];
        if (B[k] == A[i])
            k++;
        if (k == b)
            k = prefix[k - 1],
            solution.push_back(i - b + 1);
    }
    cout << solution.size() << "\n";
    for (int i = 0; i < min(1000, (int)solution.size()); i++)
        cout << solution[i] << " ";
}