Pagini recente » Cod sursa (job #2110579) | Cod sursa (job #2579124) | Cod sursa (job #995253) | Cod sursa (job #346967) | Cod sursa (job #1321472)
#include <cstdio>
#include <fstream>
#include <cstring>
#define nmax 2000005
#define mod1 666013
#define mod2 31115
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[nmax],b[nmax];
int h1[nmax],h2[nmax];
int ha1,ha2;
int n,m,c1,c2;
int match[2005],nr;
void Hashing()
{
int i;
c1=1;c2=1;
for (i=0;i<n;i++) c1=c1*100%mod1;
for (i=0;i<n;i++) c2=c2*100%mod2;
h1[0]=b[0]-'A';h2[0]=b[0]-'A';
//primul
for (i=1;i<n;i++)
h1[i]=(h1[i-1]*100+ (b[i]-'A') )%mod1;
for (i=n;i<=m;i++)
h1[i]=(h1[i-1]*100+ (b[i]-'A')-(b[i-n]-'A')*c1 )%mod1;
//al doilea
for (i=1;i<n;i++)
h2[i]=(h2[i-1]*100+ (b[i]-'A') )%mod2;
for (i=n;i<=m;i++)
h2[i]=(h2[i-1]*100+ (b[i]-'A')-(b[i-n]-'A')*c2 )%mod2;
for (i=0;i<n;i++)
ha1=(ha1*100+(a[i]-'A')) %mod1;
for (i=0;i<n;i++)
ha2=(ha2*100+(a[i]-'A')) %mod2;
for (i=0;i<m;i++)
if (h1[i]==ha1&&h2[i]==ha2) {
nr++;
if (nr<=1000) match[nr]=i;
}
}
int main()
{
int i,j;
f.getline(a,nmax);
n=strlen(a);
f.getline(b,nmax);
m=strlen(b);
Hashing();
g<<nr<<'\n';
if (nr<=1000)
for (i=1;i<=nr;i++) g<<match[i]-n+1<<' ';
else
for (i=1;i<=1000;i++) g<<match[i]-n+1<<' ';
return 0;
}