Cod sursa(job #1832623)

Utilizator Arina2003Arina Aioanei Arina2003 Data 20 decembrie 2016 17:02:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>

using namespace std;

#define nmax 2000005

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

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

void make_prefix(void)
{
    int i, q = 0;

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

int main()
{
    int i, q = 0, n1 = 0;
    f>>a>>b;
    for (; (a[m] >= 'A' && a[m] <= 'Z') || (a[m] >= 'a' && a[m] <= 'z') || (a[m] >= '0' && a[m] <= '9'); ++m);
    for (; (b[n] >= 'A' && b[n] <= 'Z') || (b[n] >= 'a' && b[n] <= 'z') || (b[n] >= '0' && b[n] <= '9'); ++n);
    for (i = m; i; --i) a[i] = a[i-1]; a[0] = ' ';
    for (i = n; i; --i) b[i] = b[i-1]; b[0] = ' ';

    make_prefix();

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

    return 0;
}