Cod sursa(job #3030375)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 17 martie 2023 17:19:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
const int NMAX=2000005;

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s[NMAX], t[NMAX], a[NMAX];
int n, m, pi[NMAX], d[NMAX];
int ans[NMAX];

void pii(char []);

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    int i, k=0, lg=0;
    fin>>a;
    for(i=0; a[i]; i++) s[i+1]=a[i];
    n=i;
    fin>>a;
    for(i=0; a[i]; i++) t[i+1]=a[i];
    m=i;
    pii(s);
    for(i=1; i<=m; i++)
    {
        while(k>0 && t[i]!=s[k+1]) k=pi[k];
        if(t[i]==s[k+1]) k++;
        d[i]=k;
        if(k==n) ans[++lg]=i-n;
    }
    fout<<lg<<'\n';
    for(i=1; i<=min(1000, lg); i++) fout<<ans[i]<<' ';
    return 0;
}

void pii(char s[])
{
    int k=0, i;
    pi[1]=0;
    for(i=2; i<=n; i++)
    {
        while(k>0 && s[i]!=s[k+1]) k=pi[k];
        if(s[i]==s[k+1]) k++;
        pi[i]=k;
    }
}