Pagini recente » Cod sursa (job #1925403) | Cod sursa (job #2580746) | Cod sursa (job #1050543) | Cod sursa (job #1843973) | Cod sursa (job #1727845)
#include<fstream>
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;
}