Pagini recente » Cod sursa (job #2830843) | Cod sursa (job #2592874) | Cod sursa (job #281693) | Cod sursa (job #796739) | Cod sursa (job #3176891)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 666013
#define VMAX 200000
#define HBASE1 128
#define HBASE2 243
#define HSIZE1 666013
#define HSIZE2 1000007
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pwr(int a,int b,int mod)
{
if(b==0)return 1;
int p = pwr(a,b/2,mod)%mod;
if(b%2)
{
return p*p*a%mod;
}
return p*p%MOD;
}
int gethash(char *s,int len,int base,int hsize)
{
int hval=0;
for(int i=0;i<len;i++)
{
hval = (hval * base + s[i])%hsize;
}
return hval;
}
bool cmp(char *a , char *b)
{
int i=0;
while(i<strlen(a) && a[i]==b[i])
{
i++;
}
return i==strlen(a);
}
int addhash(int val,char c,int base,int hsize)
{
val = (val * base + c)%hsize;
return val;
}
int removehash(int val,char c,int put,int hsize)
{
val -= c*put %hsize;
if(val < 0)
{
val += hsize;
}
return val;
}
char a[2000001];
char b[2000001];
int main()
{
fin >> a >> b;
vector<int> r;
int len = strlen(a);
int put1= pwr(HBASE1,len-1,HSIZE1);
int pathash1 = gethash(a,len,HBASE1,HSIZE1);
int currhash1 = gethash(b,len-1,HBASE1,HSIZE1);
for(int i=len-1;i<strlen(b);i++)
{
currhash1 = addhash(currhash1,b[i],HBASE1,HSIZE1);
if(currhash1==pathash1 && cmp(a,b+i-len+1))
{
r.push_back(i-len+1);
}
currhash1 = removehash(currhash1,b[i-len+1],put1,HSIZE1);
}
int n=r.size();
fout << n << "\n";
for(int i=0;i<min(n,1000);i++)
{
fout << r[i] << " ";
}
}