Pagini recente » Cod sursa (job #1315966) | Cod sursa (job #2764447) | Cod sursa (job #1207320) | Cod sursa (job #822324) | Cod sursa (job #3176880)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 666013
#define VMAX 200000
#define HASH_BASE 128
#define HASH_SIZE 666013
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pwr(int a,int b)
{
if(b==0)return 1;
int p = pwr(a,b/2)%HASH_SIZE;
if(b%2)return p*p*a%HASH_SIZE;
return p*p%HASH_SIZE;
}
int gethash(char *s,int len)
{
int hval=0;
for(int i=0;i<len;i++)
{
hval = (hval * HASH_BASE + s[i])%HASH_SIZE;
}
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)
{
val = (val * HASH_BASE + c)%HASH_SIZE;
return val;
}
int removehash(int val,char c,int put)
{
val -= c*put %HASH_SIZE;
if(val < 0)
{
val += HASH_SIZE;
}
return val;
}
char a[1000001];
char b[1000001];
int main()
{
fin >> a >> b;
vector<int> r;
int len = strlen(a);
int put=1;
for(int i=1;i<=len-1;i++)put = (put * HASH_BASE ) % HASH_SIZE;
int pathash = gethash(a,len);
int currhash = gethash(b,len-1);
for(int i=len-1;i<strlen(b);i++)
{
currhash = addhash(currhash,b[i]);
if(currhash==pathash && cmp(a,b+i-len+1))
{
r.push_back(i-len+1);
}
currhash = removehash(currhash,b[i-len+1],put);
}
fout << r.size() << "\n";
for(int i : r)
{
fout << i << " ";
}
}