Cod sursa(job #2194659)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 14 aprilie 2018 00:09:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define Nmax 2000006
using namespace std;

char A[Nmax], B[Nmax];
int prefix[Nmax], k, n, m;
vector <int> solution;

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout); //strmatch
    cin.getline(A, Nmax);
    cin.getline(B, Nmax);
    n = strlen(A);
    m = strlen(B);
    if (n > m) return !(cout << 0);
    for (int i = 1; i < n; i++) {
        while (k && A[k] != A[i])
            k = prefix[k - 1];
        if (A[k] == A[i])
            k++;
        prefix[i] = k;
    }
    k = 0;
    for (int i = 0; i < m; i++) {
        while (k && A[k] != B[i])
            k = prefix[k - 1];
        if (A[k] == B[i])
            k++;
        if (k == n) {
            if (solution.size() <= 1002)
                solution.push_back(i - n + 1);
            k = prefix[k - 1];
        }
    }

    cout << min((int)(solution.size()), 1000) << "\n";
    for (int i = 0; i < solution.size() && i < 1000; i++)
        cout << solution[i] << " ";
}