Pagini recente » Cod sursa (job #1643181) | Cod sursa (job #2599966) | Cod sursa (job #2631192) | Cod sursa (job #899734) | Cod sursa (job #2793307)
#include <fstream>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int mod=666013;
const int base=13;
int poz[1005];
int lgput(int baza, int exp)
{
if(exp==0)
return 1;
int aux=lgput(baza,exp/2);
if(exp%2==0)
return (aux*aux)%mod;
else
return ((aux*aux)%mod)*baza%mod;
}
int hashing(string str, int len)
{
int hash1,i;
i=0;
while(i<len)
{
hash1=(hash1*base+str[i])%mod;
i++;
}
return hash1;
}
int addtohash(int hash1,char c)
{
return (hash1*base+c)%mod;
}
int removefromhash(int hash1, char c, int power)
{
hash1-=c*power%mod;
if(hash1<0)
hash1+=base;
return hash1;
}
int main()
{
string pattern, text;
int patternlengh,cnt=0,k=0;
cin>>pattern;
patternlengh=pattern.size();
int patternhash=hashing(pattern,patternlengh);
int power=lgput(base,patternlengh-1);
cin>>text;
int texthash=hashing(text,patternlengh-1);
for(int i=patternlengh-1;i<text.size();i++)
{
texthash=addtohash(texthash,text[i]);
if(texthash==patternhash)
{
cnt++;
if(i-patternlengh+1<=1000)
poz[++k]=i-patternlengh+1;
}
texthash=removefromhash(texthash,text[i-patternlengh+1],power);
}
cout<<cnt<<endl;
for(int i=1;i<=k;i++)
cout<<poz[i]<<" ";
return 0;
}