Cod sursa(job #2542006)

Utilizator KaminaKaminaYo Kamina Data 9 februarie 2020 12:26:19
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char p[101], t[101], q;
int n, m, k, urm[101], nr, ceva[101], ba;
int main()
{
    in.getline(p, 101);
    in.getline(t, 101);
    m = strlen(p);
    n = strlen(t);
    urm[0] = -1;
    k = -1;
    for (int i = 1; i < m; i++) {
        while (k >=0 and p[k+1] != p[i]) k = urm[k];
        if (p[k+1] == p[i])k++;
        urm[i] = k;
    }
    k = -1;
    for (int q = 0; q < n; q++) {
        while (k >= 0 && p[k+1] != t[q])k = urm[k];
        if (p[k+1] == t[q])k++;
        if (k == m-1) ceva[ba++] = q-k, k = urm[k], nr++;
    }
    out << nr << "\n";
    for (int i = 0; i < ba; i++)out << ceva[i] << " ";

}