Cod sursa(job #3316643)

Utilizator ionicaion ionica Data 19 octombrie 2025 16:28:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

#define NM 2000010

int pi[NM],nr,n,m,nrr;
char T[NM],P[NM];///sirul si modelul (pattern-ul)
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void calculPi()
{
    int i,k;
    pi[1] = 0;
    k = 0;

    for (i = 2; i <= m; i++)
        if(P[i]==P[k+1])
        {
            k++;
            pi[i]=k;
        }
        else
        {
            while (k > 0 && P[i]!=P[k + 1])
                k = pi[k];

            if (P[i]==P[k + 1])
                k++;

            pi[i] = k;
        }
}

void KMP()
{
    vector<int>rez;
    int i,k;
    nr = 0;
    k = 0;

    for (i = 1; i <=n ; i++)
    {
        while (k > 0 && T[i]!=P[k + 1])
            k = pi[k];

        if (T[i]==P[k + 1])
            k++;

        if (k == m)
        {
            nr++;
            if(nr<=1000)
                rez.push_back(i-m);
            else
                break;
        }
    }
    fout<<nr<<'\n';
    for (i=0; i<nr; i++)
        fout <<rez[i] << ' ';
}

int main()
{
    fin >> (P+1);
    fin >> (T+1);
    m=strlen(P+1);
    n=strlen(T+1);

    calculPi();
    KMP();
    return 0;
}