Pagini recente » Cod sursa (job #2681812) | Cod sursa (job #2261363) | Cod sursa (job #1314301) | Cod sursa (job #325512) | Cod sursa (job #2730945)
#include <bits/stdc++.h>
using namespace std;
const int prime1 = 666013;
const int prime2 = 666067;
const int baza = 73;
char verif[2000001], subs[2000001], s[2000001];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void gaseste(char subs[], char s[])
{
int nSubs = strlen(subs);
int nS = strlen(s);
int hashSubs1 = 0, putere1 = 1;
int hashSubs2 = 0, putere2 = 1;
for(int i = 0; i < nSubs; i++)
{
hashSubs1 = (baza * hashSubs1 + subs[i]) % prime1;
hashSubs2 = (baza * hashSubs2 + subs[i]) % prime2;
if(i)
{
putere1 = (putere1 * baza) % prime1;
putere2 = (putere2 * baza) % prime2;
}
}
int hashS1 = 0;
int hashS2 = 0;
for(int i = 0; i < nSubs; i++)
{
hashS1 = (baza * hashS1 + s[i]) % prime1;
hashS2 = (baza * hashS2 + s[i]) % prime2;
}
int ans = 0;
if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
{
verif[0] = 1;
ans++;
}
for(int i = nSubs; i < nS; i++)
{
hashS1 = ((hashS1 - (s[i - nSubs] * putere1) % prime1 + prime1) * baza + s[i]) % prime1;
hashS2 = ((hashS2 - (s[i - nSubs] * putere2) % prime2 + prime2) * baza + s[i]) % prime2;
if(hashSubs1 == hashS1 and hashSubs2 == hashS2)
{
verif[i - nSubs + 1] = 1;
ans++;
}
}
out << ans << "\n";
for(int i = 0; i < nS; i++)
if(verif[i])
out << i << " ";
}
int main()
{
in >> subs;
in >> s;
gaseste(subs, s);
return 0;
}