Pagini recente » Cod sursa (job #2990405) | Cod sursa (job #1056346) | Cod sursa (job #2710965) | Cod sursa (job #2593461) | Cod sursa (job #952088)
Cod sursa(job #952088)
// Rolling Hash
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int NMAX = 2000005;
const int MOD1 = 100009;
const int MOD2 = 666013;
const int BASE = 104;
int i,N,M,Cnt,HashA1,HashA2,HashB1,HashB2,B1,B2;
char A[NMAX],B[NMAX];
vector<int> Sol;
vector<int>::iterator it;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A+1,B+1);
N=strlen(A+1); M=strlen(B+1);
B1=B2=1;
for(i=1;i<=N;i++)
{
HashA1=(HashA1*BASE+A[i])%MOD1;
HashA2=(HashA2*BASE+A[i])%MOD2;
B1=(B1*BASE)%MOD1;
B2=(B2*BASE)%MOD2;
}
for(i=1;i<=N;i++)
{
HashB1=(HashB1*BASE+B[i])%MOD1;
HashB2=(HashB2*BASE+B[i])%MOD2;
}
if(HashB1==HashA1 && HashB2==HashA2)
{
Cnt++;
if(Cnt<=1000) Sol.push_back(0);
}
for(i=N+1;i<=M;i++)
{
HashB1=(((HashB1*BASE)%MOD1-(B[i-N]*B1)%MOD1+MOD1)%MOD1+B[i])%MOD1;
HashB2=(((HashB2*BASE)%MOD2-(B[i-N]*B2)%MOD2+MOD2)%MOD2+B[i])%MOD2;
if(HashB1==HashA1 && HashB2==HashA2)
{
Cnt++;
if(Cnt<=1000) Sol.push_back(i-N);
}
}
printf("%d\n",Cnt);
for(it=Sol.begin();it!=Sol.end();it++) printf("%d ",*it);
return 0;
}