Cod sursa(job #2434448)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 1 iulie 2019 22:18:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#define NMAX 4000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,t,sir="";
int n,m,pi[NMAX],i,j,nr;
int main()
{
    f>>s>>t;
    n=s.size();
    m=t.size();
    sir=s+'#'+t;
    //cout<<sir;
    for(i=1;i<sir.size();i++)
    {
        j=pi[i-1];
        while(j>0 && sir[i]!=sir[j])
        {
            j=pi[j-1];
        }
        if(sir[i]==sir[j])
        {
            j++;
        }
        pi[i]=j;
    }
    for(i=n+1;i<sir.size();i++)
    {
        if(pi[i]==n)
        {
            nr++;
        }
    }
    g<<nr<<"\n";
    nr=min(nr,1000);
    for(i=n+1;i<sir.size() && nr>0;i++)
    {
        if(pi[i]==n)
        {
            g<<i-2*n<<" ";
            nr--;
        }
    }
    return 0;
}