Pagini recente » Cod sursa (job #2715469) | Cod sursa (job #1188044) | Cod sursa (job #1952749) | Cod sursa (job #1777778) | Cod sursa (job #1800029)
#include <bits/stdc++.h>
using namespace std;
const int m1 = 100000007;
int h[2000001], b[2000001];
int baza = 17;
int cheie;
int i, n, m, contor, raspuns[2000001];
char c[2000000], s[2000000];
int main()
{
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin.getline(c, 2000000);
fin.getline(s, 2000000);
for (i = strlen(c)-1; i>=0; --i)
cheie = (cheie*baza + c[i])%m1;
for (i = strlen(s)-1; i>=0; --i)
h[i] = (h[i+1]*baza +s[i])%m1;
n = strlen(s);
m = strlen(c);
b[0] = 1;
for (i = 1; i<=n; ++i)
b[i] = (b[i-1]*baza)%m1;
for (i = m-1; i < n; ++i)
{
if (cheie == ((h[i-m+1]-(h[i+1]*b[m])%m1)%m1))
{
raspuns[contor] = i-m+1;
++contor;
}
}
fout << contor << '\n';
for (i=0; i<contor; ++i)
fout << raspuns[i] << " ";
return 0;
}