Cod sursa(job #2194672)

Utilizator bpalaniciPalanici Bogdan bpalanici Data 14 aprilie 2018 00:22:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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;

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

int main() {
    fin.getline(B, Nmax);
    fin.getline(A, Nmax);
    m = strlen(B);
    n = strlen(A);
    for (int i = 1; i < m; 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 < n; i++) {
        while (k && B[k] != A[i])
            k = prefix[k - 1];
        if (B[k] == A[i])
            k++;
        if (k == m) {
            if (solution.size() < 1000)
                solution.push_back(i - m + 1);
            k = prefix[k - 1];
        }
    }

    fout << solution.size() << "\n";
    for (int i = 0; i < solution.size(); i++)
        fout << solution[i] << " ";
}