Cod sursa(job #2746096)

Utilizator toda.emanuelatoda emanuela toda.emanuela Data 27 aprilie 2021 14:46:40
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define minim(a, b) ((a < b) ? a : b)
#define Nmax 2000004
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char x[Nmax],y[Nmax];
int pi[Nmax],val[1050];
void construire()
{
    int n,k,i;
    n=strlen(x);
    k=0;
    pi[0]=0;
    for(i=2;i<n;i++)
    {
        while(k>0&&(x[i]!=x[k+1]))
            k=pi[k];
        if(x[k]==x[i])
            k++;
        pi[i]=k;
    }

}
int n,m,z=0,k,i;
int main()
{
    f.getline(x,Nmax);
    f.getline(y,Nmax);
    m=strlen(y);
    n=strlen(x);
    construire();
    k=0;
    for(i=0;i<m;i++)
    {
        while(k>0&&(y[i]!=x[k+1]))
            k=pi[k];

        if(y[i]==x[k+1])
            k++;

        if(k==n-1)
        {
            k=pi[n];
            ++z;
            val[z]=i-n+1;
        }
    }

    g<<z<<'\n';
    for(i=1;i<=z;i++)
        g<<val[i]<<" ";
    return 0;
}