Cod sursa(job #2056400)

Utilizator victorobamavictor olaru victorobama Data 4 noiembrie 2017 11:31:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <string.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int lnga,lngb,i,pi[2000005],q,pos[2000005],n;
char a[2000005],b[2000005];


void deplasare()
{
     f.getline(a,105);lnga=strlen(a);
   f.getline(b,105);lngb=strlen(b);

    for(i=lnga;i;i--)a[i]=a[i-1];a[0]=' ';
    for(i=lngb;i;i--)b[i]=b[i-1];b[0]=' ';

}


void prefix()
{
    int i, q = 0;
    for(i=2,pi[1]=0;i<=lnga;++i)
    {
        while(q && a[q+1] != a[i]) q=pi[q];
        if(a[q+1]==a[i])q++;
        pi[i]=q;

    }


}

int main()
{
   deplasare();



   for(i=1;i<=lngb;i++)
    {
        while( q && a[q+1] != b[i]) q=pi[q];
        if(a[q+1]==b[i])++q;

        if(q==lnga)
        {

        q=pi[lnga];

        ++n;

        pos[n]=i-lnga;
        }

    }
     g<<n<<'\n';
    if(n>1000) n=1000;
   for(i=1;i<=n;i++) g<<pos[i]<<' ';
   g<<'\n';

   f.close();
   g.close();

    return 0;
}