Cod sursa(job #2445934)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 6 august 2019 11:23:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char ch,a[2000005],b[2000005];
int pi[2000005],pi2[2000005],i,j,nr1,nr2,nr, nrafis;
int main()
{
    while(f.get(ch))
    {
        if(ch=='\n')
            break;
        a[++nr1]=ch;
    }
    while(f.get(ch))
    {
        if(ch=='\n')
            break;
        b[++nr2]=ch;
    }
    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;
}