Pagini recente » Cod sursa (job #2221012) | Cod sursa (job #691519) | Cod sursa (job #1084524) | Cod sursa (job #2823765) | Cod sursa (job #3260978)
#include <bits/stdc++.h>
#define B 62
#define P 10000019
#define Q 777013
using namespace std;
ifstream fin("cuvant2.in");
ofstream fout("cuvant2.out");
/**
'0' = 0
'1' = 1
...
'9' = 9
'A' = 10
'B' = 11
...
'Z' = 35
'a' = 36
'b' = 37
...
'z' = 61
*/
char a[2000005], b[2000005];
int n, m, sol[2000005], len;
int main()
{
int i, coda, codb, j, p62, p62q;
int coda1, codb1;
fin >> a >> b;
n = strlen(a); m = strlen(b);
/// formam p62 = B^(n-1)
p62q = p62 = 1;
for (i = 1; i < n; i++)
{
p62 = p62 * B % P;
p62q = p62q * B % Q;
}
/// formam codul asociat lui a
coda = coda1 = 0;
for (i = 0; i < n; i++)
{
if (a[i] <= '9') j = a[i] - '0';
else if (a[i] <= 'Z') j = a[i] - 'A' + 10;
else j = a[i] - 'a' + 36;
coda = (coda * B + j) % P;
coda1 = (coda1 * B + j) % Q;
}
/// formam primul codb si codb1
codb = codb1 = 0;
for (i = 0; i < n; i++)
{
if (b[i] <= '9') j = b[i] - '0';
else if (b[i] <= 'Z') j = b[i] - 'A' + 10;
else j = b[i] - 'a' + 36;
codb = (codb * B + j) % P;
codb1 = (codb1 * B + j) % Q;
}
if (codb == coda && codb1 == coda1)
sol[++len] = 0;
for (i = n; i < m; i++)
{
/// adaugam cifra b[i], scoatem b[i-n]
if (b[i-n] <= '9') j = b[i-n] - '0';
else if (b[i-n] <= 'Z') j = b[i-n] - 'A' + 10;
else j = b[i-n] - 'a' + 36;
codb = (codb - j * p62 % P + P) * B;
codb1 = (codb1 - j * p62q % Q + Q) * B;
if (b[i] <= '9') j = b[i] - '0';
else if (b[i] <= 'Z') j = b[i] - 'A' + 10;
else j = b[i] - 'a' + 36;
codb = (codb + j) % P;
codb1 = (codb1 + j) % Q;
if (codb == coda && codb1 == coda1)
sol[++len] = i - n + 1;
}
fout << len << "\n";
for (i = 1; i <= len; i++)
fout << sol[i] << " ";
return 0;
}