Pagini recente » Cod sursa (job #2510130) | Atasamentele paginii Clasament brasov_city_challenge | Atasamentele paginii Clasament grafuri | Istoria paginii utilizator/alexia1029384756 | Cod sursa (job #2439968)
#include <bits/stdc++.h>
using namespace std;
#define cin fi
#define cout fo
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int NMAX = 2e6 + 5;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int baza = 62;
int n, m;
char A[NMAX], B[NMAX];
vector <int> rez;
int total;
inline int getMod(long long x, int M)
{
return x - x / M * M;
}
char cod(char x)
{
if ('a' <= x && x <= 'z')
return x - 'a';
else if ('A' <= x && x <= 'Z')
return x - 'A' + ('z' - 'a') + 1;
else if ('0' <= x && x <= '9')
return x - '0' + ('Z' - 'A' + ('z' - 'a') + 1) + 1;
}
int main()
{
cin >> A + 1 >> B + 1;
m = strlen(A + 1);
n = strlen(B + 1);
for (int i = 1; i <= m; i++)
A[i] = cod(A[i]);
for (int i = 1; i <= n; i++)
B[i] = cod(B[i]);
if (m > n)
{
cout << 0;
return 0;
}
long long maska1 = 0, maska2 = 0;
long long maskb1 = 0, maskb2 = 0;
for (int i = 1; i <= m; i++)
{
maska1 = getMod(maska1 * baza + A[i], MOD1);
maska2 = getMod(maska2 * baza + A[i], MOD2);
maskb1 = getMod(maskb1 * baza + B[i], MOD1);
maskb2 = getMod(maskb2 * baza + B[i], MOD2);
}
long long p1 = 1, p2 = 1;
for (int i = 1; i < m; i++)
{
p1 = getMod(p1 * baza, MOD1);
p2 = getMod(p2 * baza, MOD2);
}
if (maska1 == maskb1 && maska2 == maskb2)
total++, rez.push_back(1);
for (int i = m + 1; i <= n; i++)
{
maskb1 = (maskb1 - p1 * B[i - m]);
while (maskb1 < 0)
maskb1 += MOD1;
maskb2 = (maskb2 - p2 * B[i - m]);
while (maskb2 < 0)
maskb2 += MOD2;
maskb1 = getMod(maskb1 * baza + B[i], MOD1);
maskb2 = getMod(maskb2 * baza + B[i], MOD2);
if (maskb1 == maska1 && maskb2 == maska2)
{
total++;
if (rez.size() < 1000)
rez.push_back(i - m + 1);
}
}
cout << total << "\n";
for (auto x: rez)
cout << x - 1 << " ";
return 0;
}