Cod sursa(job #2449354)

Utilizator filiptudose2007Tudose Filip filiptudose2007 Data 19 august 2019 13:40:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char c,a[2000005],b[2000005];
int pi[2000005],pi2[2000005],i,j,nr1,nr2,nr, nrafis;
int main()
{
    while(f.get(c))
    {
        if(c=='\n')
            break;
        a[++nr1]=c;
    }
    while(f.get(c))
    {
        if(c=='\n')
            break;
        b[++nr2]=c;
    }
    pi[1]=0;
    j=1;
    for(i=2; i<=nr1; ++i)
    {
        if(a[i]==a[j])
        {
            pi[i]=j;
            j++;
        }
        else while(j!=1)
            {
                j=pi[j-1]+1;
                if(a[i]==a[j])
                {
                    pi[i]=j;
                    j++;
                    break;
                }
            }
    }
    pi2[1]=0;
    j=1;
    for(i=1; i<=nr2; ++i)
    {
        if(b[i]==a[j])
        {
            pi2[i]=j;
            j++;
        }
        else while(j!=1)
            {
                j=pi[j-1]+1;
                if(b[i]==a[j])
                {
                    pi2[i]=j;
                    j++;
                    break;
                }
            }
    }
    for(i=1; i<=nr2; ++i)
        if(pi2[i]==nr1)
            nr++;
    g<<nr<<'\n';
    if(nr<=1000)
    {
        for(i=1; i<=nr2; ++i)
        {
            if(pi2[i]==nr1)
                g<<i-nr1<<' ';
        }
    }
    else
    {
        for(i=1; i<=nr2 && nrafis<1000; ++i)
            if(pi2[i]==nr1)
            {
                g<<i-nr1<<' ';
        nrafis++;
            }
    }
    return 0;
}