Pagini recente » Cod sursa (job #693040) | Cod sursa (job #236431) | Cod sursa (job #934472) | oni_sim1 | Cod sursa (job #1279447)
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#define B1 29
#define B2 101
#define MOD1 101119
#define MOD2 104033
using namespace std;
void read_data(string &A, string &B)
{
ifstream f("strmatch.in");
f>>A>>B;
f.close();
}
void write_data(const int &nr_sol, const vector<int> &sol)
{
ofstream g("strmatch.out");
g<<nr_sol<<"\n";
for(auto it = sol.begin();it != sol.end();++it)
g<<*it<<" ";
g.close();
}
int main()
{
string A, B;
read_data(A, B);
int a_size = A.size(), b_size = B.size();
int keyA1 = 0, keyA2 = 0, pow1 = 1, pow2 = 1, keyB1 = 0, keyB2 = 0;
int nr_sol = 0;
vector<int> sol;
for(int i=0; i < a_size ; ++i)
{
keyA1 = ((keyA1 * B1) % MOD1 + A[i])%MOD1;
keyA2 = ((keyA2 * B2) % MOD2 + A[i])%MOD2;
if(i!=0)
{
pow1 *= B1;
pow1 %= MOD1;
pow2 *= B2;
pow2 %= MOD2;
}
}
for(int i=0;i < b_size;++i)
{
if(i < a_size)
{
keyB1 = ((keyB1 * B1)%MOD1 + B[i])%MOD1;
keyB2 = ((keyB2 * B2)%MOD2 + B[i])%MOD2;
}
else {
keyB1 = (((keyB1 - pow1 * B[i-a_size])%MOD1 + MOD1) * B1 + B[i])%MOD1;
keyB2 = (((keyB2 - pow2 * B[i-a_size])%MOD2 + MOD2) * B2 + B[i])%MOD2;
}
if(keyB1 == keyA1 && keyB2 == keyA2)
{
if(nr_sol < 1000)
sol.push_back(i - a_size + 1);
++nr_sol;
}
}
write_data(nr_sol, sol);
return 0;
}