Cod sursa(job #2191876)

Utilizator lonca.sorin1Lonca Sorin lonca.sorin1 Data 3 aprilie 2018 22:40:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000020
#define minim(a, b) ((a < b) ? a : b)

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int n, m;
char a[NMax], b[NMax];
int pi[NMax], pos[1024];

void make_prefix()
{
    int i, q = 0;
    for (i = 2, pi[1] = 0; i <= n; ++i)
    {
        while (q && a[q + 1] != a[i])
            q = pi[q];
        if (a[q + 1] == a[i])
            ++q;
        pi[i] = q;
    }
}

int main()
{
    int q = 0, n1 = 0;

    f.getline(a, NMax);
    f.getline(b, NMax);

    n = strlen(a);
    m = strlen(b);

    for (int i = n; i; --i)
        a[i] = a[i - 1];
    a[0] = ' ';

    for (int i = m; i; --i)
        b[i] = b[i - 1];
    b[0] = ' ';

    make_prefix();

    for (int i = 1; i <= m; ++i)
    {
        while(q && a[q + 1] != b[i])
            q = pi[q];
        if (a[q + 1] == b[i])
            ++q;
        if (q == n)
        {
            q = pi[n];
            ++n1;
            if (n1 <= 1000)
                pos[n1] = i - n;
        }
    }
    g<<n1<<'\n';
    for (int i = 1; i <= minim(n1, 1000); ++i)
        g<<pos[i]<<" ";
    return 0;
}