Cod sursa(job #2284550)

Utilizator ButumAndreiButum Andrei ButumAndrei Data 17 noiembrie 2018 11:30:58
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{int n=2,m=3,nr=0;
int h=100007,j=100021;


char c[200000],s[200000];
f.get(c,200000);
f.get();
f.get(s,200000);
int q=strlen(c);
long long hprin1=0;
long long hprin2=0;
long long hsec1=0;
long long hsec2=0;


for(int i=1;i<=q;i++)
{
    hprin1=hprin1+c[i-1]*pow(n,q-i);
    hprin1%h;
   hprin2=hprin2+c[i-1]*pow(m,q-i);
   hprin2%j;
}
for(int i=1;i<=q;i++)
{
    hsec1=hsec1+s[i-1]*pow(n,q-i);
    hsec1%h;
    hsec2=hsec2+s[i-1]*pow(m,q-i);
    hsec2%j;
}
long long poz[200000];
int p=strlen(s);
for(int i=1;i<p-q+1;i++)
{if(hprin1==hsec1&&hprin2==hsec2)
    {
    poz[nr++]=i-1;
    }


      hsec1=hsec1-(s[i-1]*pow(n,q-1));
      hsec1=hsec1*n;
      hsec1+=s[i+2];
        hsec1%h;
      hsec2=hsec2-(s[i-1]*pow(m,q-1));
      hsec2=hsec2*m;
      hsec2+=s[i+2];
  hsec2%j;
}
g<<nr<<"\n";
for(int i=0;i<nr;i++)
    g<<poz[i]<<" ";
    return 0;
}