Pagini recente » Cod sursa (job #448166) | Cod sursa (job #683479) | Cod sursa (job #726796) | Cod sursa (job #132760) | Cod sursa (job #3176906)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 666013
#define P 73
#define HSIZE1 100021
#define HSIZE2 100007
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001];
char b[2000001];
bool ans[2000001];
int main()
{
fin >> a >> b;
if(strlen(a) > strlen(b))
{
fout << 0;
return 0;
}
int m = strlen(b);
int cnt=0;
int put1=1,put2=1;
int strhash1=0,strhash2=0;
int pathash1=0,pathash2=0;
int len = strlen(a);
for(int i=0;i<len;i++)
{
pathash1 = (pathash1 * P + a[i])%HSIZE1;
pathash2 = (pathash2 * P + a[i])%HSIZE2;
strhash1= (strhash1 * P + b[i])%HSIZE1;
strhash2 = (strhash2 * P + b[i])%HSIZE2;
if(i)
{
put1 = put1 * P % HSIZE1;
put2 = put2 * P % HSIZE2;
}
}
if(strhash1 == pathash1 && strhash2 == pathash2)
{
ans[0]=1;
}
for(int i=len;i<m;i++)
{
strhash1 = ((strhash1 - (b[i-len]*put1) % HSIZE1 + HSIZE1)*P + b[i])%HSIZE1;
strhash2 = ((strhash2 - (b[i-len]*put2) % HSIZE2 + HSIZE2)*P + b[i])%HSIZE2;
if(strhash1 == pathash1 && strhash2 == pathash2)
{
ans[i-len+1]=1;
++cnt;
}
}
fout << cnt << " ";
int k=0;
for(int i=0;i<m && k<1000;i++)
{
if(ans[i])
{
fout << i << " ";
++k;
}
}
}