Pagini recente » Cod sursa (job #1653703) | Cod sursa (job #497417) | Istoria paginii planificare/sedinta-20080303 | Cod sursa (job #226590) | Cod sursa (job #2985529)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int P=71,M1=100007, M2=100021;
vector<int> results;
int pH1(string a)
{
long long p=1,rez=0;
for (int i=a.size()-1;i>=0;i--)
{
rez=(rez+(p*a[i])%M1)%M1;
p=(p*P)%M1;
}
return rez;
}
int pH2(string a)
{
long long p=1,rez=0;
for (int i=a.size()-1;i>=0;i--)
{
rez=(rez+(p*a[i])%M2)%M2;
p=(p*P)%M2;
}
return rez;
}
int main()
{
string S,g;
in >> g >> S;
if(g.size() > S.size())
{
out << '0' << '\n';
return 0;
}
int hashg1=pH1(g), hashg2=pH2(g);
string test=S.substr(0,g.size());
int hashTest1=pH1(test), hashTest2=pH2(test);
int putere1=1, putere2 = 1;
for (int i=1; i<=g.size()-1; i++)
{
putere1=(putere1*P)%M1;
putere2 = (putere2*P)%M2;
}
int ct=0,oldHash1 = hashTest1, oldHash2 = hashTest2;
if (hashg1==hashTest1 && hashg2 == hashTest2)
{
ct++;
results.push_back(0);
}
//out << hashg << '\n' << '\n';
//out << putere << '\n';
//out << hashTest << '\n' << '\n';
for (int i = 1; i < S.size() - g.size() + 1; i++)
{
//string temp = S.substr(i, g.size());
//out << temp << '\n';
//out << S[i-1] << " " << S[g.size() + i - 1] << '\n';
int newHash1 = ((oldHash1 - S[i-1]*putere1)%M1 + M1) * P + S[g.size()+i-1];
newHash1=newHash1%M1;
int newHash2 = ((oldHash2 - S[i-1]*putere2)%M2 + M2) * P + S[g.size()+i-1];
newHash2=newHash2%M2;
//out << newHash << '\n';
//int temph = pH(temp);
//out << temph << '\n' << '\n';
if (newHash1==hashg1 && newHash2==hashg2)
{
ct++;
if(results.size() < 1000)
{
results.push_back(i);
}
}
oldHash1=newHash1;
oldHash2=newHash2;
}
out << ct << '\n';
for(int i =0; i < results.size(); i++)
{
out << results[i] << " ";
}
out << '\n';
return 0;
}