Pagini recente » Cod sursa (job #1205684) | Cod sursa (job #3250370) | Cod sursa (job #2850794) | Cod sursa (job #1005454) | Cod sursa (job #1904634)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
const int MOD1 = 1000000000 + 7;
const int C1 = 61;
const int MOD2 = 1000000000 + 9;
const int C2 = 67;
int N, M;
string A, B;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
N = A.size();
M = B.size();
A = " " + A;
B = " " + B;
int h1A = 0;
int h2A = 0;
int C1N = 1;
int C2N = 1;
for (int i = 1; i <= N; ++ i) {
h1A = (1LL * h1A * C1 + (A[i] - 'A')) % MOD1;
h2A = (1LL * h2A * C2 + (A[i] - 'A')) % MOD2;
C1N = (1LL * C1N * C1) % MOD1;
C2N = (1LL * C2N * C2) % MOD2;
}
vector <int> sol;
int h1B = 0;
int h2B = 0;
for (int i = 1; i <= M; ++ i) {
h1B = (1LL * h1B * C1 + (B[i] - 'A')) % MOD1;
h2B = (1LL * h2B * C2 + (B[i] - 'A')) % MOD2;
if (i >= N + 1) {
h1B = (h1B - 1LL * (B[i - N] - 'A') * C1N) % MOD1;
if (h1B < 0)
h1B += MOD1;
h2B = (h2B - 1LL * (B[i - N] - 'A') * C2N) % MOD2;
if (h2B < 0)
h2B += MOD2;
}
if (i >= N && h1A == h1B && h2A == h2B)
sol.push_back(i - N);
}
cout << sol.size() << '\n';
if (sol.empty())
cout << '\n';
else {
cout << sol[0];
for (int i = 1; i < 1000 && i < sol.size(); ++ i)
cout << ' ' << sol[i];
cout << '\n';
}
return 0;
}