Pagini recente » Cod sursa (job #1290238) | Cod sursa (job #314901) | Cod sursa (job #2408097) | Cod sursa (job #2109831) | Cod sursa (job #1798946)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000001],s[2000001];
int q1=100007,q2=100021,kmax,z,x,y,xp,yp,v[1002];
int main()
{
int i;
f>>p;
f.get();
f>>s;
if(strlen(p)>strlen(s))
g<<0;
else{
int b1=1,b2=1;
for(i=1;i<strlen(p);i++)
{
b1=(b1*128)%q1;
b2=(b2*128)%q2;
}
for(i=0;i<strlen(p);i++)
{
x=((x*128)%q1+s[i])%q1;
y=((y*128)%q2+s[i])%q2;
xp=((xp*128)%q1+p[i])%q1;
yp=((yp*128)%q2+p[i])%q2;
}
if(x==xp&&y==yp)
{
kmax++;
v[++z]=0;
}
for(i=1;i<=strlen(s)-strlen(p)+1;i++)
{
x=((x+q1-(s[i-1]*b1)%q1)*128+s[i+strlen(p)-1])%q1;
y=((y+q2-(s[i-1]*b2)%q2)*128+s[i+strlen(p)-1])%q2;
if(x==xp&&y==yp){kmax++;if(z<1000)v[++z]=i;}}
g<<kmax<<'\n';
for(i=1;i<=z;i++)
g<<v[i]<<" ";}
return 0;
}