Cod sursa(job #2910317)

Utilizator suimerchantsui merchant suimerchant Data 19 iunie 2022 13:32:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define DIM 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
char A[DIM+2], B[DIM+2];
int P[DIM+2], sol[1001];
int a, b, i, L, nr;
int main ()
{
    fin>>A+1;
    fin>>B+1;
    a = strlen(A+1);
    b = strlen(B+1);
    L = 0;
    P[1] = 0;
    for (int i=2; i<=a; i++)
    {
        while (L!=0 && A[i] != A[L+1])
        {
            L = P[L];
        }
        if (A[i] == A[L+1])
        {
            L++;
        }
        P[i] = L;
    }
    L = 0;
    for (i=1; i<=b; i++)
    {
        while (L != 0 && B[i]!=A[L+1])
            L = P[L];
        if (B[i] == A[L+1])
        {
            L++;
        }
        if (L == a)
        {
            nr++;
            if (nr<=1000)
            {
                sol[nr] = i-a;
            }
            L = P[L];
        }
    }
    fout<<nr<<"\n";
    for (int i=1; i<=min(1000, nr); i++)
    {
        fout<<sol[i]<<" ";
    }
    return 0;
}