Pagini recente » Borderou de evaluare (job #2015099) | Borderou de evaluare (job #210319) | Borderou de evaluare (job #962707) | Borderou de evaluare (job #739085) | Cod sursa (job #2985197)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
long int P=17,M=1000000007;
vector<int> results;
long int pH(string a)
{
int p=1,rez=0;
for (int i=a.size()-1;i>=0;i--)
{
rez=rez+p*a[i];
p=p*P;
p=p%M;
rez=rez%M;
}
return rez;
}
int main()
{
string S,g;
in >> g >> S;
if(g.size() > S.size())
{
out << '0' << '\n';
return 0;
}
long int hashg=pH(g);
string test=S.substr(0,g.size());
long int hashTest=pH(test);
long int putere=1;
for (int i=1; i<=g.size()-1; i++)
{
putere=putere*P;
}
long int ct=0,oldHash=hashTest;
if (hashg==hashTest)
{
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';
long int newHash=(oldHash-S[i-1]*putere)*P+S[g.size()+i-1];
newHash=newHash%M;
//out << newHash << '\n';
long int temph = pH(temp);
//out << temph << '\n' << '\n';
if (newHash==hashg)
{
ct++;
if(results.size() < 1000)
{
results.push_back(i);
}
}
oldHash=newHash;
}
out << ct << '\n';
for(int i =0; i < results.size(); i++)
{
out << results[i] << " ";
}
out << '\n';
return 0;
}