Cod sursa(job #2745917)

Utilizator BogdanNPPupeza Bogdan BogdanNP Data 27 aprilie 2021 10:24:50
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int maxN = 2000005;
int n, m;
char a[maxN], b[maxN];
int pref[maxN];
int poz[1001];
int cnt;

void Citire();
void KMP();
void Prefix();
void Afisare();

int main()
{
    Citire();
    Prefix();
    KMP();
    Afisare();

    return 0;
}

void Citire()
{
    a[0] = ' ';
    b[0] = ' ';
    fin >> (a+1) >> (b+1);
    n = strlen(a) - 1;
    m = strlen(b) - 1;

}

void Prefix()
{
    pref[1] = 0;
    int k = 0;
    for (int i = 2; i <= n; ++i)
    {
        while ((k > 0) && (a[k + 1] != a[i]) )
            k = pref[k];
        if (a[k + 1] == a[i])
            ++k;
        pref[i] = k;
    }
}

void KMP()
{
    int q = 0;
    for (int i = 1; i <= m; ++i)
    {
        while ((q > 0) && (a[q + 1] != b[i]))
            q = pref[q];
        if (a[q + 1] == b[i])
            ++q;
        if (q == n)
        {
            poz[i - n + 1] = 1;
            cnt++;
        }

    }
}

void Afisare()
{
    fout << cnt << '\n';
    int minim = min(m, 1000);
    for (int i = 1; i <= minim; ++i)
    {
        if(poz[i] == 1)
            fout << i - 1 << ' ';

    }
}