Cod sursa(job #2750067)

Utilizator toda.emanuelatoda emanuela toda.emanuela Data 9 mai 2021 19:44:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define Nmax 2000006
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char x[Nmax],y[Nmax];
int pi[Nmax],val[1050];
int minim(int a,int b)
{
    if(a>b) return b;
    return a;
}
void asezare(int n, char s[])
{
    int i;
    for(i=n;i>0;i--)
        s[i]=s[i-1];

    s[n+1]=0;
}
void construire()
{
    int n,k,i;
    n=strlen(x);
    k=0;
    pi[1]=0;
    for(i=2;i<=n;i++)
    {
        while(k>0&&(x[i]!=x[k+1]))
            k=pi[k];
        if(x[k+1]==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);
    asezare(n,x);
    asezare(m,y);
    construire();
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k>0&&(y[i]!=x[k+1]))
            k=pi[k];

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

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

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