Pagini recente » Cod sursa (job #730116) | Cod sursa (job #2953237) | Cod sursa (job #2885520) | Cod sursa (job #938077) | Cod sursa (job #2749754)
#include <bits/stdc++.h>
#define P 9987671
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000002];
char b[2000002];
int n , m;
int cod[256];
vector <int> poz;
int main()
{
int h , h1, j = 0, pw = 1;
fin >> a >> b;
for (int i = '0'; i <= '9'; i++)
cod[i] = j++;
for (int i = 'a'; i <= 'z'; i++)
cod[i] = j++;
for (int i = 'A'; i <= 'Z'; i++)
cod[i] = j++;
/// construim pe h
h = 0;
for (n = 0; a[n] != 0; n++)
{
h = (h * 62 + cod[a[n]]) % P;
if (n < strlen(a) - 1) pw = pw * 62 % P;
}
/// parcurg fiecare secv de lungime n din b
/// formez primul cod h1 cu primele n car. din b
h1 = 0;
int nrPotriviri = 0;
for (int i = 0; i < n ; i++)
h1 = (h1 * 62 + cod[b[i]]) % P;
if (h == h1) nrPotriviri++;
for (int i = n; b[i] != 0; i++)
{
h1 = ((h1 - cod[b[i - n]] * pw % P + P) * 62 + cod[b[i]]) % P;
if (h1 == h)
{
nrPotriviri++;
if (nrPotriviri <= 1000) poz.push_back(i - n + 1);
}
}
fout << nrPotriviri << "\n";
for (auto j : poz)
fout << j << " ";
return 0;
}