Pagini recente » Cod sursa (job #2879881) | Cod sursa (job #2033475) | Cod sursa (job #560872) | Cod sursa (job #1858630) | Cod sursa (job #3184938)
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
#define mod1 1000007
#define mod2 666013
std::vector<long long>ans;
std::string word;
std::string seq;
long long p=97, p2=53, 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(long long index=seqSize-1; index>=0; --index)
{
seqKey1=seqKey1%mod1+(seq[index]*V)%mod1;
localKey1=localKey1%mod1+(word[index]*V)%mod1;
seqKey2=seqKey2%mod2+(seq[index]*V2)%mod2;
localKey2=localKey2%mod2+(word[index]*V2)%mod2;
if(index>0)
{
V=(V*p)%mod1;
V2=(V2*p2)%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*p2+x)%mod2;
}
void solve()
{
if(localKey1==seqKey1 && localKey2==seqKey2)
{
ans.push_back(0);
++nr;
}
long long size=word.size();
for(long long index=seqSize; index<size; ++index)
{
if(localKey1==seqKey1 && localKey2==seqKey2)
{
ans.push_back(index-seqSize);
++nr;
if(nr==1000)
break;
}
roll(word[index], word[index-seqSize]);
}
long long ansSize=ans.size();
fout<<ansSize<<'\n';
for(int index=0; index<ansSize; ++index)
fout<<ans[index]<<' ';
}
int main()
{
read();
if(seq.size()>word.size())
{
fout<<"0\n";
return 0;
}
preCalc();
solve();
return 0;
}