Pagini recente » Profil usureluflorian | Diferente pentru problema/tproc intre reviziile 5 si 4 | Rezultatele filtrării | Borderou de evaluare (job #562119) | Cod sursa (job #2772703)
#include <bits/stdc++.h>
#define P 9987671
#define Q 9981121
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
int n;
int cod[256], poz[1005], m;
int main()
{
int i, j;
int h, H, h1, h2, pw, PW, cnt;
j = 0;
for (i = '0'; i <= '9'; i++)
cod[i] = j++;
for (i = 'a'; i <= 'z'; i++)
cod[i] = j++;
for (i = 'A'; i <= 'Z'; i++)
cod[i] = j++;
fin >> a >> b;
h = H = 0;
for (n = 0; a[n] != 0; n++)
{
h = (h * 62 + cod[a[n]]) % P;
H = (H * 62 + cod[a[n]]) % Q;
}
pw = PW = 1;
for (i = 1; i < n; i++)
{
pw = pw * 62 % P;
PW = PW * 62 % Q;
}
h1 = h2 = 0;
cnt = 0;
for (i = 0; i < n; i++)
{
h1 = (h1 * 62 + cod[b[i]]) % P;
h2 = (h2 * 62 + cod[b[i]]) % Q;
}
if (h1 == h && h2 == H)
{
cnt++;
poz[++m] = 0;
}
for (i = n; b[i] != 0; i++)
{
h1 = ((h1 - cod[b[i - n]] * pw % P + P) * 62 + cod[b[i]]) % P;
h2 = ((h2 - cod[b[i - n]] * PW % Q + Q) * 62 + cod[b[i]]) % Q;
if (h1 == h && h2 == H)
{
cnt++;
if (m < 1000) poz[++m] = i - n + 1;
}
}
fout << cnt << "\n";
for (i = 1; i <= m; i++)
fout << poz[i] << " ";
fin.close();
fout.close();
return 0;
}