Pagini recente » Cod sursa (job #2265350) | Cod sursa (job #225187) | Cod sursa (job #2815111) | Cod sursa (job #1736942) | Cod sursa (job #2694781)
#include<fstream>
#include<cstring>
#include<iostream>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
int i, nr=0, H, H2, has, has2, v[1005];
char m[2000003], n[2000004];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>m>>n;
int l1= strlen(m);
int l2= strlen(n);
for(int i=0; i<l1; i++)
{
int x= m[i];
H = (H*P + x)%MOD1;
H2= (H2*P + x)%MOD2;
}
for(int i= 0; i<l1;i++)
{
int y= n[i];
has = (has*P + y)%MOD1;
has2 = (has2 *P+ y)%MOD2;
}
int pow1=1, pow2=1;
for(int i=1; i<l1;i++)
{
pow1=(pow1* P)%MOD1;
pow2= (pow2 * P)%MOD2;
}
if(has== H && has2== H2)
{
nr++;
}
for(int i= l1; i<l2;i++)
{
has = (has-pow1*(n[i-l1]))%MOD1+ MOD1;
has= (has*P +(n[i]))%MOD1;
has2 = (has2-pow2*(n[i-l1]))%MOD2+MOD2;
has2= (has2*P +(n[i]))%MOD2;
if(has==H && has2== H2)
{
nr++;
if(nr<=1000)
v[nr]=i-l1+1;
}
}
cout << nr<<endl;
for(int i=1 ;i<=nr && i<=1000;i++)
cout<<v[i]<<" ";
}