Cod sursa(job #1812399)

Utilizator radu.leonardoThe Doctor radu.leonardo Data 22 noiembrie 2016 01:09:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

short t[2000001];
unsigned short sol[1001], n, m, nr,i=2,k=0,pos1=0,pos2=0;
string a, b;
int main()
{
    f>>a>>b;
    n=a.size();
    m=b.size();

    if(m==n)
    {   if(a==b) g<<1<<"\n"<<0;
        else g<<0;
        return 0;
    }
    t[0]=-1;t[1]=0;
    while(i<n)
        if (a[i-1]==a[k])t[i++]=++k;
        else
            if (k>0)  k=t[k];
            else t[i++]=0;

     while(pos1+pos2<m)
        if (a[pos2]==b[pos1+pos2])
          if (pos2==n-1)
            {    if (++nr<1000) sol[nr-1]=pos1;
                 if (t[pos2] > -1)  pos1+=pos2-t[pos2],pos2=t[pos2];
                 else pos2=0,pos1++;
            }
            else pos2++;
        else if (t[pos2]>-1)  pos1+=pos2-t[pos2],pos2=t[pos2];
             else pos2=0,pos1++;

    g<<nr<<"\n";
    for (int i=0;i<(nr<1000?nr:1000);i++)  g<<sol[i]<<" ";
}