Pagini recente » Cod sursa (job #328273) | Cod sursa (job #1673149) | Cod sursa (job #1153411) | Cod sursa (job #1579538) | Cod sursa (job #1983155)
#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]-'A');
NRP%=MOD;
NRT+=Prod*(T[i]-'A');
NRT%=MOD;
if (i!=0)
{
Prod*=26;
Prod%=MOD;
}
}
if (NRT==NRP && Verify(0)==true)
SOL.push_back(0);
for (i=LP; i<LT; i++)
{
nr=Prod*(T[i-LP]-'A');
nr%=MOD;
NRT-=nr;
if (NRT<0)
NRT=MOD+(NRT % MOD);
NRT*=26;
NRT%=MOD;
NRT+=T[i]-'A';
if (NRT>=MOD)
NRT-=MOD;
if (NRT==NRP && Verify(i-LP+1)==true)
{
SOL.push_back(i-LP+1);
if (SOL.size()==1000)
break;
}
}
fout << SOL.size() << '\n';
for (it=SOL.begin(); it!=SOL.end(); it++)
fout << *it << " ";
fin.close();
fout.close();
return 0;
}