Pagini recente » Cod sursa (job #1148513) | Cod sursa (job #1283456) | Cod sursa (job #1614414) | Cod sursa (job #1289917) | Cod sursa (job #2028070)
#include <bits/stdc++.h>
using namespace std;
char a[2000005];
char b[2000005];
int d[2000005];
int nrsol = -1, sol[1000];
int la, lb;
void precalc()
{
int q = -1;
d[0] = -1;
for(int i = 1; i < la; i++)
{
while(q != -1 && a[q + 1] != a[i])
q = d[q];
if(a[q + 1] == a[i])
q++;
d[i] = q;
}
}
void kmp()
{
precalc();
int q = -1;
for(int i = 0; i < lb; i++)
{
while(q != -1 && b[i] != a[q + 1])
q = d[q];
if(b[i] == a[q + 1])
q++;
if(q == la - 1)
{
++nrsol;
if(nrsol < 1000)
sol[nrsol] = i - la + 1;
q = d[q];
}
}
}
void rabin()
{
const unsigned int k1 = 33, k2 = 31;
unsigned int ha1 = 0, ha2 = 0, pk1 = 1, pk2 = 1, hb1 = 0, hb2 = 0;
for(int i = 0; i < la; i++)
{
ha1 = ha1 * k1 + a[i];
ha2 = ha2 * k2 + a[i];
hb1 = hb1 * k1 + b[i];
hb2 = hb2 * k2 + b[i];
}
for(int i = 1; i < la; i++)
{
pk1 = pk1 * k1;
pk2 = pk2 * k2;
}
if(ha1 == hb1 && ha2 == hb2)
{
++nrsol;
if(nrsol < 1000)
sol[nrsol] = 1;
}
for(int i = la; i < lb; i++)
{
hb1 = hb1 - pk1 * b[i - la];
hb2 = hb2 - pk2 * b[i - la];
hb1 = hb1 * k1 + b[i];
hb2 = hb2 * k2 + b[i];
if(ha1 == hb1 && ha2 == hb2)
{
++nrsol;
if(nrsol < 1000)
sol[nrsol] = i - la + 1;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", a, b);
la = strlen(a);
lb = strlen(b);
rabin();
nrsol++;
printf("%d\n", nrsol);
int k = min(1000, nrsol);
for(int i = 0; i < k; i++)
printf("%d ", sol[i]);
return 0;
}