Pagini recente » Cod sursa (job #2045058) | Cod sursa (job #2401447) | Cod sursa (job #149847) | Cod sursa (job #1957972) | Cod sursa (job #1402089)
#include <fstream>
#include <string>
#include <vector>
#define MOD1 100007
#define MOD2 100021
#define P 73
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A, B;
vector < int > V;
int h1_A, h2_A, h1_B, h2_B, sol, P1, P2;
void Verif(int p)
{
if (h1_A == h1_B && h2_A == h2_B) {
sol++;
V.push_back(p);
}
}
void Write_Data()
{
fout << sol << '\n';
for (auto it : V) {
fout << it << ' ';
}
fout.close();
}
int main()
{
fin >> A >> B;
P1 = P2 = 1;
for (int i = 0; i < A.size(); i++)
{
h1_A = (h1_A * P + A[i]) % MOD1;
h2_A = (h2_A * P + A[i]) % MOD2;
if (i) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
h1_B = (h1_B * P + B[i]) % MOD1;
h2_B = (h2_B * P + B[i]) % MOD2;
}
Verif(0);
for (int i = A.size(); i < B.size(); i++)
{
h1_B = (((h1_B - (P1 * B[i - A.size()])) % MOD1 + MOD1) * P + B[i]) % MOD1;
h2_B = (((h2_B - (P2 * B[i - A.size()])) % MOD2 + MOD2) * P + B[i]) % MOD2;
Verif(i - A.size() + 1);
}
Write_Data();
return 0;
}