Cod sursa(job #3329012)

Utilizator contandrei3Andrei Mihai contandrei3 Data 11 decembrie 2025 15:41:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#define NMAX 2000000
char A[NMAX+5],B[NMAX+5];
int n,m,cnt,lps[NMAX+5];
queue <int> q;
void buildPrefix()
{
    int i, k=0;
    n=strlen(A);
    for (i=2; i<=n; i++)
    {
        while (k && A[k] != A[i-1]) k = lps[k];
        if (A[k] == A[i-1]) k++;
        lps[i]=k;
    }
}
void potrivire()
{
    int i, k = 0;;
    m=strlen(B);
    for (int i = 0; i < m; i++)
    {
        while (k && A[k] != B[i]) k = lps[k];
        if (A[k] == B[i]) k++;
        if (k==n)
        {
            cnt++;
            if (cnt<=1000) q.push(i-n+1);
        }
// poziția pe care începe subșirul A de lungime n în B, știind că se termină pe poziția i
    }
}
int main()
{
    fin.getline (A,NMAX);
    fin.getline (B,NMAX);
    buildPrefix();
    potrivire();
    fout<<cnt<<'\n';
    while (!q.empty())
    {
        fout<<q.front()<<" ";
        q.pop();
    }
    return 0;
}