Pagini recente » Cod sursa (job #2918653) | Cod sursa (job #3225735) | Cod sursa (job #1660293) | Cod sursa (job #1462420) | Cod sursa (job #1538183)
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000010],b[2000010];
int i,j,hash1,hash2,p1=1,p2=1,h1,h2,n,m,mod1=100003,mod2=100069;
queue<int> Q;
int main()
{
f>>a>>b;
n=strlen(a)-1;
m=strlen(b)-1;
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;
}
for(i=0;i<=n;i++)
{
p1=(p1*257)%mod1;
p2=(p2*257)%mod2;
}
if(h1==hash1&&h2==hash2)
Q.push(0);
for(i=n+1;i<=m;i++)
{
h1=((h1*257+b[i]-b[i-(1+n)]*p1)%mod1+mod1)%mod1;
h2=((h2*257+b[i]-b[i-(1+n)]*p2)%mod2+mod2)%mod2;
if(h1==hash1&&h2==hash2)
Q.push(i-n);
}
i=1;
g<<Q.size()<<'\n';
while(i<=1000&&!Q.empty())
{
i++;
g<<Q.front()<<" ";
Q.pop();
}
return 0;
}