Pagini recente » Cod sursa (job #2604381) | Cod sursa (job #468742) | Cod sursa (job #2089514) | Cod sursa (job #1661186) | Cod sursa (job #1892312)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAXLEN 2000001
char s[MAXLEN], p[MAXLEN];
int sl, pl;
#define PRIME 73
#define MOD 100021
typedef unsigned long long LL;
int strlen(char *p)
{
int i = 0;
while(*p) i++,p++;
return i;
}
void citire()
{
scanf("%s %s ",p,s);
sl = strlen(s);
pl = strlen(p);
}
LL compute(char *a,int len)
{
LL rez = 0;
LL prime_power = 1;
for(int i=0;i<len;i++)
{
rez += (a[i]*prime_power);
rez %= MOD;
prime_power *= PRIME;
prime_power %= MOD;
}
return rez;
}
LL rolling_hash;
LL prime_power;
LL pow(LL x, LL power)
{
if(power==1)
return x % MOD;
if((power&1)==0)
{
LL rez = pow(x,power>>1) % MOD;
return (rez * rez) % MOD;
}
return pow(x,power-1);
}
void compute_prime_power()
{
prime_power=pow(PRIME,pl);
}
void roll(char add, char rem)
{
// cout<<"remove "<<rem<<" adding "<<add<<endl;
rolling_hash -= rem;
rolling_hash /= PRIME;
rolling_hash += (add*prime_power);
rolling_hash %= MOD;
}
bool check(int start)
{
for(int i=0,j=start; i< pl; i++, j++)
if(p[i]!=s[j])
return 0;
return 1;
}
vector<int> result;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
compute_prime_power();
//cout<<prime_power<<endl;
LL pattern_hash = compute(p,pl);
// cout<<pattern_hash<<endl;
rolling_hash = compute(s,pl);
for(int i=pl; i< sl; i++)
{
//cout<<rolling_hash<<endl;
if(pattern_hash == rolling_hash)
{
if(check(i-pl))
{
result.push_back(i-pl);
}
}
roll(s[i],s[i-pl]);
}
int result_size = result.size();
printf("%d\n",result_size);
for(int i=0;i<result_size;i++)
printf("%d ",result[i]);
return 0;
}