Pagini recente » Cod sursa (job #836207) | Cod sursa (job #2854050) | Cod sursa (job #778321) | Cod sursa (job #99187) | Cod sursa (job #2675181)
#define NMAX 2000005
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long lli;
char s1[NMAX], s2[NMAX];
lli a[1005];
lli l1, l2, nr;
class Hash{
private:
lli n, m, power, value;
public:
Hash(){n = 0, m = 0, power = 0, value = 0;}
Hash(int nn, int mm) {n = nn; m = mm;}
void init(char *s, lli len)
{
power = 1;
value = 0;
for(lli i = len-1; i >= 0; --i)
{
value = (value + power*s[i]%m)%m;
if(i)
power = (power*n)%m;
}
}
void roll(char toRemove, char toAdd)
{
value = (((value - (1LL*toRemove*power)%m+m)*n)%m + toAdd)%m;
}
bool operator==(const Hash &other) const {
return value == other.value;
}
};
void read()
{
scanf("%s\n%s", s1, s2);
l1 = strlen(s1);
l2 = strlen(s2);
}
void solve()
{
Hash shor[2]{{31, 40099}, {53, 319993}};
Hash lo[2]{{31, 40099}, {53, 319993}};
for(int i = 0; i < 2; ++i)
{
shor[i].init(s1, l1);
lo[i].init(s2, l1);
}
if(shor[0] == lo[0] && shor[1] == lo[1])
a[++nr] = 0;
for(int i = l1; i < l2; ++i)
{
for(int k = 0; k < 2; ++k)
lo[k].roll(s2[i-l1], s2[i]);
if(shor[0] == lo[0] && shor[1] == lo[1])
{
if(nr <= 1000)
a[++nr] = i-l1+1;
else nr++;
}
}
}
void write()
{
int vmin = (nr >= 1000)?1000:nr;
printf("%d\n", nr);
for(int i = 1; i <= nr; ++i)
printf("%d ", a[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
read();
solve();
write();
return 0;
}