Cod sursa(job #2726313)

Utilizator emanuel2186Lugojan Emanuel emanuel2186 Data 20 martie 2021 18:29:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[Nmax];
char B[Nmax];
int P[Nmax];
int rez;
void citire()
{
    fin>>A;
    fin>>B;
}
void prefix()
{
    char p[Nmax];
    strcpy(p, A);
    strcpy(A + 1, p);

    strcpy(p, B);
    strcpy(B + 1, p);
    A[0] = B[0] = ' ';
    int i, j = 0;

    for(i=2; A[i]; i++)
    {
        while(j && A[j + 1] != A[i])
        {
            j = P[j];
        }
        if(A[j + 1] == A[i])
        {
            j++;
        }
        P[i] = j;
    }
}
vector<int>poz;
void afisare()
{
    fout<<rez<<"\n";
    for(int i=0; i<poz.size() ;i++)
    {
        fout<<poz[i]<<" ";
    }
}
void rezolvare()
{
    int j = 0;
    int N = strlen(A) - 1;
    for(int i=1; B[i]; i++)
    {
        while(j && A[j + 1] != B[i])
        {
            j = P[j];
        }
        if(A[j + 1] == B[i])
            j++;
        if(j == N)
        {
            rez++;
            if (rez <= 1000)
                poz.push_back(i - N);
        }
    }
    afisare();
}
int main()
{
    citire();
    prefix();
    rezolvare();
    return 0;
}