Pagini recente » Cod sursa (job #2160216) | Cod sursa (job #198226) | Cod sursa (job #979742) | Cod sursa (job #856737) | Cod sursa (job #1278674)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char A[2000012],B[2000012];
int mod1=299777,mod2=299771,ANS[2000012];
int main()
{
fin>>A>>B;
int lunga=strlen(A);
int lungb=strlen(B);
int hashA1=0;
int hashA2=0;
int putmax1=1;
int putmax2=1;
for(int i=0;i<lunga;i++)
{
hashA1=(hashA1*71+A[i])%mod1;
hashA2=(hashA2*71+A[i])%mod2;
if(i)
{
hashA1=(hashA1*71)%mod1;
hashA2=(hashA2*71)%mod2;
}
}
if(lunga>lungb)
{
fout<<"0";
return 0;
}
int hashB1=0;
int hashB2=0;
for(int i=0;i<lunga;i++)
{
hashB1=(hashB1*71+B[i])%mod1;
hashB2=(hashB2*71+B[i])%mod2;
}
int sol=0;
if(hashA1==hashB1 and hashA2==hashB2)
{
ANS[0]=1;
sol++;
}
//fout<<sol<<endl;
//sol=1;
for (int i=lunga;i<lungb;i++)
{
hashB1=((hashB1-(B[i-lunga]*putmax1)%mod1+mod1)*71+B[i])%mod1;
hashB2=((hashB2-(B[i-lunga]*putmax2)%mod2+mod2)*71+B[i])%mod2;
if(hashB1==hashA1 and hashB2==hashA2)
ANS[i-lunga+1]=1,sol++;
}
fout<<sol<<endl;
sol=0;
for(int i=0;i<lungb and sol<1000;i++)
if(ANS[i]!=0)
sol++,
fout<<i;
fout<<endl;
return 0;
}