Pagini recente » Cod sursa (job #1760917) | Cod sursa (job #2175431) | Cod sursa (job #2400381) | Cod sursa (job #1462752) | Cod sursa (job #3184941)
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
#define mod1 1000007
#define mod2 666013
#define p 97
std::vector<long long>ans;
std::string word;
std::string seq;
long long nr=0;
long long seqKey1, localKey1, seqSize, V=1, V2=1;
long long seqKey2, localKey2;
void read()
{
fin>>seq;
fin>>word;
}
void preCalc()
{
seqSize=seq.size();
for(int index=0; index<seqSize; ++index)
{
seqKey1=(seqKey1*p+seq[index])%mod1;
seqKey2=(seqKey2*p+seq[index])%mod2;
if(index)
{
V=(V*p)%mod1;
V2=(V2*p)%mod2;
}
}
}
void roll(char x, char erased)
{
localKey1=(localKey1-(erased*V)%mod1)%mod1+mod1;//hash1
localKey1=(localKey1*p+x)%mod1;
localKey2=(localKey2-(erased*V2)%mod2)%mod2+mod2;//hash2
localKey2=(localKey2*p+x)%mod2;
}
void solve()
{
if(seq.size()>word.size())
{
fout<<"0\n";
return;
}
for(int index=0; index<seqSize; ++index)
{
localKey1=(localKey1*p+word[index])%mod1;
localKey2=(localKey2*p+word[index])%mod2;
}
if(localKey1==seqKey1 && localKey2==seqKey2)
{
ans.push_back(0);
++nr;
}
long long size=word.size();
for(long long index=seqSize; index<size; ++index)
{
roll(word[index], word[index-seqSize]);
if(localKey1==seqKey1 && localKey2==seqKey2)
{
ans.push_back(index-seqSize+1);
++nr;
}
}
fout<<nr<<'\n';
for(int index=0; index<nr && index<1000; ++index)
fout<<ans[index]<<' ';
}
int main()
{
read();
preCalc();
solve();
return 0;
}