Pagini recente » Cod sursa (job #3038492) | Cod sursa (job #2679977) | Cod sursa (job #1390309) | Cod sursa (job #3284665) | Cod sursa (job #2675054)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
#define p 73
#define MOD1 100007
#define MOD2 100021
char s1[2000009],s2[2000009];
int p1=1,p2=1;
int ans[1009],k,n,m;
int HASH1,HASH2 ,Hash1,Hash2;
int main(){
f>>s1>>s2;
n=strlen(s1);
m=strlen(s2);
for(int i=0;i<n;i++){
HASH1=(HASH1*p+s1[i])%MOD1;
HASH2=(HASH2*p+s1[i])%MOD2;
if(i!=0)
p1=(p1*p)%MOD1,p2=(p2*p)%MOD2;
}
for(int i=0;i<n;i++){
Hash1=(Hash1*p+s2[i])%MOD1;
Hash2=(Hash2*p+s2[i])%MOD2;
}
if(HASH1==Hash1&&HASH2==Hash2)
ans[++k]=0;
for(int i=n;i<m;i++){
Hash1=((Hash1-(s2[i-n]*p1)%MOD1+MOD1)*p+s2[i])%MOD1;
Hash2=((Hash2-(s2[i-n]*p2)%MOD2+MOD2)*p+s2[i])%MOD2;
if(HASH1==Hash1&&HASH2==Hash2){
k++;
if(k<=1000)
ans[k]=i-n+1;
}
}
g<<k<<"\n";
for(int i=1;i<=min(1000,k);i++)
g<<ans[i]<<' ';
}