Pagini recente » Cod sursa (job #1772774) | Cod sursa (job #1442441) | Cod sursa (job #57852) | Cod sursa (job #2136970) | Cod sursa (job #1920581)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define NMAX 2000005
#define MOD1 10007
#define MOD2 666013
#define NR1 27
#define NR2 29
using namespace std;
char a[NMAX], b[NMAX];
int n, m, v1, v2, h1, h2, pow1 = 1, pow2 = 1;
vector<int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s ",a,b);
n = strlen(a);
m = strlen(b);
v1 = v2 = 0;
for(int i=0; i<n; ++i)
{
v1 = ((1LL*v1 * NR1) % MOD1 + a[i]) % MOD1;
v2 = ((1LL*v2 * NR2) % MOD2 + a[i]) % MOD2;
if(i)
{
pow1 =(pow1 * NR1) % MOD1;
pow2 =(pow2 * NR2) % MOD2;
}
}
for(int i=0;i<n;i++)
{
h1 = ((1LL*h1 * NR1) % MOD1 + b[i]) % MOD1;
h2 = ((1LL*h2 * NR2) % MOD2 + b[i]) % MOD2;
}
if(h1==v1 && h2==v2)
{
sol.push_back(0);
}
for(int i=n;i<m;i++)
{
h1 = ((h1 - (b[i-n]*pow1) % MOD1 + MOD1)* NR1 + b[i]) % MOD1;
h2 = ((h2 - (b[i-n]*pow2) % MOD2 + MOD2)* NR2 + b[i]) % MOD2;
if(h1==v1 && h2==v2)
{
sol.push_back(i-n+1);
}
}
printf("%d\n",sol.size());
unsigned long long s = sol.size();
if(s>1000)
s=1000;
for(int i=0;i<s;i++)
printf("%d ",sol[i]);
return 0;
}