Pagini recente » Cod sursa (job #740409) | Cod sursa (job #982793) | Cod sursa (job #785054) | Cod sursa (job #2946657) | Cod sursa (job #982878)
Cod sursa(job #982878)
#include <fstream>
#include <string>
#include <vector>
const long long pb = 257;
const long long MOD = 1000000007;
long long pow(long long x, long long a)
{
if(a == 0) return 1;
if(a == 1) return x % MOD;
if(a % 2 == 0) return (pow((x * x) % MOD, a / 2)) % MOD;
return (x * pow((x * x) % MOD, a / 2)) % MOD;
}
long long getHash(std::string& str, long long a, long long b)
{
long long ret = 0;
for(long long i = a; i < b; i++)
ret = ret * pb + str[i], ret %= MOD;
return ret;
}
bool comps(std::string& str, std::string& lstr, long long start)
{
for(long long i = 0; i < str.length(); i++)
if(str[i] != lstr[start + i]) return false;
return true;
}
long long rabin(std::string& str, std::string& lstr, std::vector<long long>& myV)
{
long long nr = 0;
long long comp = getHash(str, 0, str.length());
long long ret = getHash(lstr, 0, str.length());
long long power = pow(pb, str.length());
if(ret == comp)
{
if(comps(str, lstr, 0))
{
myV.push_back(0);
nr++;
}
}
for(long long i = str.length(); i < lstr.length(); i++)
{
ret = ret * pb + lstr[i];
ret %= MOD;
ret -= (power * lstr[i - str.length()]) % MOD;
if(ret < 0) ret += MOD;
if(ret == comp)
{
if(comps(str, lstr, i - str.length() + 1))
{
if(myV.size() < 1000) myV.push_back(i - str.length() + 1);
nr++;
}
}
}
return nr;
}
int main()
{
std::ifstream in("strmatch.in");
std::ofstream out("strmatch.out");
std::string str, lstr;
getline(in, str);
getline(in, lstr);
std::vector<long long> myV;
long long nr = rabin(str, lstr, myV);
out << nr << '\n';
for(std::vector<long long>::iterator it = myV.begin(); it != myV.end(); it++)
out << *it << ' ';
return 0;
}