# Cod sursa(job #1867475)

Utilizator Data 4 februarie 2017 09:56:23 Potrivirea sirurilor 100 cpp done Arhiva educationala 1.47 kb
``````#include <fstream>
#include <vector>
#include <cstring>
#define b 27
#define b1 29
#define MOD 10007
#define MOD1 66013
#define DIM 2000020
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector <int> sol;
vector <int> :: iterator it;
int val,val1,h,h1,x,x1,p,p1,i,nr,nrsol;
char s[DIM],s1[DIM];
int main()
{
f.getline(s,2000001);
f.getline(s1,2000001);
x=strlen(s);
x1=strlen(s1);
val=val1=0;
h=h1=0;
p=p1=1;
if(x>x1)
{
g<<0<<'\n';
f.close();
return 0;
}
for( i=0 ; i< x ; i++ )
{
val = ( val*b + int (s[i]) ) %MOD;
val1 = ( val1*b1 + int(s[i]) ) %MOD1;
h = ( h*b + int (s1[i]) ) %MOD;
h1 = ( h1*b1 + int(s1[i]) ) %MOD1;
if ( i!=1 )
{
p = ( p * b ) % MOD;
p1 = ( p1 * b1 ) % MOD1;
}
}
if(h==val && h1==val1)
{
nr++;
sol.push_back(0);
}
for( i=x ; i< x1; i++ )
{
h =(( h-( int (s1[i-x])*p ) % MOD + MOD) * b + int(s1[i])) % MOD;
h1 =(( h1- (int (s1[i-x])*p1 ) % MOD1 + MOD1) * b1 + int(s1[i])) % MOD1;
if(h==val && h1==val1)
{
nr++;
if(nr<=1000)
sol.push_back(i-x+1);
}
}
g<<nr<<'\n';
for(it=sol.begin();it!=sol.end();++it)
{
g<<*it<<" ";
nrsol++;
if(nrsol>=1000)
break;
}
return 0;
}
``````