Pagini recente » Cod sursa (job #2119898) | Cod sursa (job #1805499) | Cod sursa (job #1450868) | Cod sursa (job #2457295) | Cod sursa (job #1805676)
#include<fstream>
#include<string.h>
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
int h1, h2, he1, he2;
char s1[2000010], s2[2000010];
int a[1010], nr;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main()
{
int l1, l2;
in >> s1 >> s2;
l1 = strlen(s1);
l2 = strlen(s2);
int p1 = 1, p2 = 1;
for (int i = 0;i < l1;++i)
{
h1 = (h1*P + s1[i]) % MOD1;
h2 = (h2*P + s1[i]) % MOD2;
if (i)
{
p1 = (p1*P) % MOD1;
p2 = (p2*P) % MOD2;
}
}
for (int i = 0;i < l1;++i)
{
he1 = (he1*P + s2[i]) % MOD1;
he2 = (he2*P + s2[i]) % MOD2;
}
if (h1 == he1 && h2 == he2)
a[++nr] = 0;
for (int i = 1;i <= l2 - l1;++i)
{
he1 = (((he1 - (s2[i - 1] * p1) % MOD1 + MOD1)*P) % MOD1 + s2[i + l1 - 1]) % MOD1;
he2 = (((he2 - (s2[i - 1] * p2) % MOD2 + MOD2)*P) % MOD2 + s2[i + l1 - 1]) % MOD2;
if (h1 == he1 && h2 == he2)
{
++nr;
if (nr <= 1000)
a[nr] = i;
}
}
out << nr << '\n';
for (int i = 1;i <= nr && i <= 1000;++i)
out << a[i] << " ";
return 0;
}