Pagini recente » Rating Johannes Dragulanescu (Johannes) | Cod sursa (job #1763632) | Cod sursa (job #170835) | Cod sursa (job #1672068) | Cod sursa (job #1228728)
#include<fstream>
#include<iostream>
#include<string>
#include<list>
#define MOD1 99991
#define MOD2 99871
#define B1 10
#define B2 23
using namespace std;
void read(string &A, string &B)
{
ifstream f("strmatch.in");
f>>A>>B;
f.close();
}
void write(const list<int> &sol)
{
ofstream g("strmatch.out");
g<<sol.size()<<"\n";
for(auto it = sol.begin(); it != sol.end(); ++it)
g<<*it<<" ";
g.close();
}
int main()
{
string A, B;
read(A, B);
int size_A = A.length();
int size_B = B.length();
int keyA1 = 0, keyA2 = 0, keyB1 = 0, keyB2 = 0, PB1 = 1, PB2 = 1;
list<int> sol;
for(int i=0; i < size_A;++i)
{
keyA1 = ((keyA1 * B1) + A[i])%MOD1;
keyA2 = ((keyA2 * B2) + A[i])%MOD2;
if(i != 0)
{
PB1 = (PB1 * B1)%MOD1;
PB2 = (PB2 * B2)%MOD2;
}
}
for(int i=0; i < size_B; ++i)
{
if(i >= size_A)
{
keyB1 = (((keyB1 - PB1 * B[i-size_A]) % MOD1 + MOD1) * B1 + B[i]) % MOD1;
keyB2 = (((keyB2 - PB2 * B[i-size_A]) % MOD2 + MOD2) * B2 + B[i]) % MOD2;
}
else
{
keyB1 = ((keyB1 * B1) + B[i])%MOD1;
keyB2 = ((keyB2 * B2) + B[i])%MOD2;
}
if(keyB1 == keyA1 && keyB2 == keyA2)
sol.push_back(i - size_A + 1);
}
write(sol);
return 0;
}