Cod sursa(job #2389579)

Utilizator andrei32576Andrei Florea andrei32576 Data 27 martie 2019 11:44:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
using namespace std;

#define NMax 2000005

int n, m, i, nr;
char A[NMax], B[NMax];
int pi[NMax], pos[1005];

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

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

int main()
{
    f.getline(A, NMax);
    f.getline(B, NMax);

    n=strlen(A);
    n++;
    A[n]='\0';
    for (i=n-1;i>0;i--)
        A[i] = A[i-1];
    A[0] = ' ';

    m=strlen(B);
    m++;
    B[m]='\0';
    for (i=m-1;i>0;i--)
        B[i] = B[i-1];
    B[0] = ' ';
    n--, m--;

    make_prefix();

    nr = 0;
    int q = 0;
    for (i=1;i<=m;i++)
    {
        while (q>0 && A[q+1]!=B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            q++;
        if (q == n)
        {
            q = pi[n];
            nr++;
            if (nr<=1000)
                pos[nr] = i - n;
        }
    }

    g<<nr<<"\n";
    for (i=1;i<=min(nr,1000);i++)
        g<<pos[i]<<" ";

    f.close();
    g.close();
    return 0;
}