Pagini recente » Cod sursa (job #2459660) | Cod sursa (job #2990358) | Cod sursa (job #1353215) | Cod sursa (job #1206011) | Cod sursa (job #1904650)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
const int MOD1 = 1000000000 + 7;
const int C1 = 257;
//const int MOD2 = 1000000000 + 9;
//const int C2 = 263;
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();
if (N > M) {
cout << "0\n";
return 0;
}
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]) % MOD1;
//h2A = (1LL * h2A * C2 + A[i]) % 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]) % MOD1;
//h2B = (1LL * h2B * C2 + B[i]) % MOD2;
if (i >= N + 1) {
h1B = (h1B - 1LL * B[i - N] * C1N) % MOD1;
if (h1B < 0)
h1B += MOD1;
//h2B = (h2B - 1LL * B[i - N] * 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;
}