Cod sursa(job #2451941)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 28 august 2019 22:15:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n,i,j,m,pi[3000001],pi2[3000001],nr,kk;
char c,a[3000001],b[3000001];
int main ()
{
while (true)
{
        in.get (c);
    if (c==' '||c=='\n') break;
    else a[++n]=c;
}
while (true)
{
    in.get (c);
    if (c==' '||c=='\n') break;
    else b[++m]=c;

}
j=1;
    for(i=2;i<=n;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;
                }
            }
    }
    j=1;
    for(i=1;i<=m;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<=m;i++)
        if(pi2[i]==n)
            nr++;
            out<<nr<<'\n';
        for (i=1;i<=m&&kk<1000;i++)
        {
            if (pi2[i]==n) {out<<i-n<<" "; kk++;}
        }
            return 0;
}