Pagini recente » Cod sursa (job #2331984) | Cod sursa (job #2667517) | Cod sursa (job #2182567) | Cod sursa (job #1797659) | Cod sursa (job #1983403)
#include <fstream>
#include <vector>
#define MOD 666013
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int LP, LT, i, j, nr;
int NRP, NRT, Prod;
vector <int> SOL;
vector <int> :: iterator it;
string P, T;
bool Verify(int K)
{
int i;
for (i=0; i<LP; i++)
if (P[i]!=T[i+K])
return false;
return true;
}
int main()
{
fin >> P >> T;
LP=P.size();
LT=T.size();
Prod=1;
for (i=LP-1; i>=0; i--)
{
NRP+=Prod*(P[i]);
NRP%=MOD;
NRT+=Prod*(T[i]);
NRT%=MOD;
if (i!=0)
{
Prod*=199;
Prod%=MOD;
}
}
if (NRT==NRP && Verify(0)==true)
SOL.push_back(0);
for (i=LP; i<LT; i++)
{
nr=Prod*(T[i-LP]);
nr%=MOD;
NRT-=nr;
if (NRT<0)
NRT=MOD+(NRT % MOD);
NRT*=199;
NRT%=MOD;
NRT+=T[i];
if (NRT>=MOD)
NRT-=MOD;
if (NRT==NRP && Verify(i-LP+1)==true)
SOL.push_back(i-LP+1);
}
fout << SOL.size() << '\n';
int K=SOL.size();
for (i=0; i<min(K, 1000); i++)
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}