Cod sursa(job #3144589)

Utilizator AdiFBubuBubuianu Adrian AdiFBubu Data 9 august 2023 02:54:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

#define NMAX 2000005

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

char A[NMAX], B[NMAX];
int d[NMAX], nA, nB, q;
int nr, p[NMAX];

void prefix()
{
    d[1] = 0;
    int q = 0;
    for(int i = 2; i <= nA; i ++)
    {
        while(q && A[q + 1] != A[i])
            q = d[q];
        if(A[q + 1] == A[i])
            q ++;
        d[i] = q;
    }
}

int main()
{
    f.getline(A, NMAX);
    f.getline(B, NMAX);
    nA = strlen(A), nB = strlen(B);
    for(int i = nA; i >= 1; i --)
        A[i] = A[i - 1];
    for(int i = nB; i >= 1; i --)
        B[i] = B[i - 1];

    prefix();

    for(int i = 1; i <= nB; i ++)
    {
        while(q && A[q + 1] != B[i])
            q = d[q];
        if(A[q + 1] == B[i])
            q ++;
        if(q == nA)
        {
            nr ++;
            q = d[nA];
            p[i - nA] = 1;
        }
    }
    g << nr << '\n';
    int val = 0;
    for(int i = 0; val != nr && val < 1000; i ++ )
        if(p[i] == 1)
            val ++, g << i << " ";
    return 0;
}