Pagini recente » Cod sursa (job #701276) | Cod sursa (job #3235973) | Cod sursa (job #292195) | Cod sursa (job #768880) | Cod sursa (job #3269877)
#include <fstream>
#include <cstring>
using namespace std;
/**
'0' = 0
'1' = 1
...
'9' = 9
'A' = 10
'B' = 11
...
'Z' = 35
'a' = 36
'b' = 37
...
'z' = 61
*/
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[2000005], b[2000005];
int n, m, sol[2000005], lungime;
int main()
{
int i, codap, codbp, j, p62, q62;
int codaq, codbq;
int B = 62;
long long P = 1000007, Q = 666013;
cin >> a >> b;
n = strlen(a); m = strlen(b);
/// formam p62, q62 = B^(n-1)
p62 = q62 = 1;
for (i = 1; i < n; i++)
{
p62 = p62 * B % P;
q62 = q62 * B % Q;
}
/// formam codul asociat lui a
codap = codaq = 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;
codap = (codap * B + j) % P;
codaq = (codaq * B + j) % Q;
}
/// formam primul codb si codb1
codbp = codbq = 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;
codbp = (codbp * B + j) % P;
codbq = (codbq * B + j) % Q;
}
if (codbp == codap && codbq == codaq)
sol[++lungime] = 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;
codbp = (codbp - j * p62 % P + P) * B;
codbq = (codbq - j * q62 % 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;
codbp = (codbp + j) % P;
codbq = (codbq + j) % Q;
if (codbp == codap && codbq == codaq)
sol[++lungime] = i - n + 1;
}
cout << lungime << "\n";
lungime = min(lungime, 1000);
for (i = 1; i <= lungime; i++)
cout << sol[i] << " ";
return 0;
}