Pagini recente » Cod sursa (job #690792) | Cod sursa (job #1385745) | Cod sursa (job #1369644) | Cod sursa (job #1460537) | Cod sursa (job #1804995)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
pair<int, int> code;
const int MOD1 = 17;
const int MOD2 = 2999999;
const int base = 30;
vector<int> sol;
void CodeA()
{
for(int i = 0; i < a.size(); ++i)
{
code.first = code.first * base + a[i];
code.first %= MOD1;
code.second = code.second * base + a[i];
code.second %= MOD2;
}
}
void rezolvare()
{
if(a.size() > b.size())
{
out << 0;
return;
}
CodeA();
pair<int, int> cCode = make_pair(0, 0); //current code
int i;
int pow1 = 1, pow2 = 1;
for(i = 0; i < a.size(); ++i)
{
cCode.first = cCode.first * base + b[i];
cCode.first %= MOD1;
cCode.second = cCode.second * base + b[i];
cCode.second %= MOD2;
if(i > 0)
{
pow1 = (pow1 * base) % MOD1;
pow2 = (pow2 * base) % MOD2;
}
}
if(code == cCode)
sol.push_back(i - a.size() + 1);
while(i < b.size())
{
cCode.first = (cCode.first - (b[i - a.size()] * pow1) % MOD1 + MOD1) * base + b[i];
cCode.first %= MOD1;
cCode.second = (cCode.second - (b[i - a.size()] * pow2) % MOD2 + MOD2) * base + b[i];
cCode.second %= MOD2;
if(code == cCode)
sol.push_back(i - a.size() + 1);
++i;
}
}
void afisare()
{
out << sol.size() << "\n";
int stop = min(1000, (int)sol.size());
for(int i = 0; i < stop; ++i)
out << sol[i] << " ";
}
int main()
{
in >> a >> b;
rezolvare();
afisare();
return 0;
}