Pagini recente » Cod sursa (job #143850) | Cod sursa (job #274634) | Cod sursa (job #1177014) | Cod sursa (job #1108319) | Cod sursa (job #2134201)
#include <fstream>
#include <string.h>
#define nmax 2000000
#define INF 1000000
#define MOD1 100031
#define MOD2 100009
#define baz 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int ans[1001];
long long act1,act2;
int main()
{
int n,m,i,sear1=0,sear2=0,rez=0,p1=1,p2=1;
f>>a;
f>>b;
m=strlen(a);
n=strlen(b);
sear1=a[0];
sear2=a[0];
for(i=1;i<m;i++)
{
sear1=(sear1*baz+a[i])%MOD1;
sear2=(sear2*baz+a[i])%MOD2;
p1=(p1*baz)%MOD1;
p2=(p2*baz)%MOD2;
}
for(i=0;i<m;i++)
{
act1=(act1*baz+b[i])%MOD1;
act2=(act2*baz+b[i])%MOD2;
}
if(act1==sear1 && act2==sear2)
{
rez++;
ans[rez]=0;
}
for(i=m;i<n;i++)
{
act1=((act1-(b[i-m]*p1)%MOD1+MOD1)*baz+b[i])%MOD1;
act2=((act2-(b[i-m]*p2)%MOD2+MOD2)*baz+b[i])%MOD2;
if(act1==sear1 && act2==sear2)
{
rez++;
ans[rez]=i-m+1;
}
}
g<<rez<<'\n';
for(i=1;i<=rez;i++)
g<<ans[i]<<' ';
return 0;
}