Pagini recente » Rating Arvinte Dobreanu Ionita (Arvinte_Dobreanu_Ionita_Iasi) | Borderou de evaluare (job #1284920) | Borderou de evaluare (job #117004) | Cod sursa (job #3274193) | Cod sursa (job #2985509)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int P=17,M=100007;
vector<int> results;
int pH(string a)
{
long long p=1,rez=0;
for (int i=a.size()-1;i>=0;i--)
{
rez=(rez+(p*a[i])%M)%M;
p=(p*P)%M;
}
return rez;
}
int main()
{
string S,g;
in >> g >> S;
if(g.size() > S.size())
{
out << '0' << '\n';
return 0;
}
int hashg=pH(g);
string test=S.substr(0,g.size());
int hashTest=pH(test);
int putere=1;
for (int i=1; i<=g.size()-1; i++)
{
putere=putere*P;
putere = putere % M;
}
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';
int newHash = ((oldHash - S[i-1]*putere)%M + M) * P + S[g.size()+i-1];
newHash=newHash%M;
//out << newHash << '\n';
//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;
}