Cod sursa(job #2451926)

Utilizator Savu_Stefan_CatalinSavu Stefan Catalin Savu_Stefan_Catalin Data 28 august 2019 20:58:50
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n,i,j,m,pi[2000001],pi2[2000001],nr;
char c,a[2000001],b[2000001];
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&&i<=1000;i++)
        {
            if (pi2[i]==n) out<<i-n<<" ";
        }
            return 0;
}