Pagini recente » Cod sursa (job #2688058) | Cod sursa (job #1016117) | Cod sursa (job #1681669) | Cod sursa (job #1527848) | Cod sursa (job #1527853)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
long long h1,h2,i,j,n,m,rest=1,p2571,p2572,hash1,nr,hash2,mod1=100003,mod2=100019;
char a[2000010],b[2000010];
queue<int> Q;
void ridput(int exp,int md)
{
while(exp>1)
{
if(exp%2==0)
{
nr=(nr*nr)%md;
exp/=2;
}
else
{
exp--;
rest=(rest*nr)%md;
}
}
nr=(nr*rest)%md;
}
int main()
{
f>>a>>b;
n=strlen(a);
m=strlen(b);
for(i=0;i<n;i++)
{
hash1=(hash1*257+a[i])%mod1;
hash2=(hash2*257+a[i])%mod2;
}
for(i=0;i<n;i++)
{
h1=(h1*257+b[i])%mod1;
h2=(h2*257+b[i])%mod2;
if(h1==hash1&&h2==hash2)
Q.push(0);
}
nr=257;
rest=1;
ridput(n,mod1);
rest=1;
p2571=nr;
nr=257;
ridput(n,mod2);
p2572=nr;
for(i=n;i<m;i++)
{
h1=(h1*257+b[i])%mod1;
h1=(h1-(b[i-n]*p2571)%mod1+mod1)%mod1;
h2=(h2*257+b[i])%mod2;
h2=(h2-(b[i-n]*p2572)%mod2+mod2)%mod2;
if(h1==hash1&&h2==hash2)
{
Q.push(i-n+1);
}
}
g<<Q.size()<<'\n';
i=1;
while(i<=1000&&!Q.empty())
{
g<<Q.front()<<" ";
Q.pop();
i++;
}
g<<'\n';
return 0;
}