Pagini recente » Cod sursa (job #1350310) | Cod sursa (job #1433136) | Cod sursa (job #2561631) | Cod sursa (job #1579950) | Cod sursa (job #1752543)
#include <fstream>
using namespace std;
long long n,m,i,k,v1,v2,p1,p2,w1,w2,q[2000005];
char a[2000005],b[2000005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a;
f>>b;
n=0;
while(a[n]) n++;
m=0;
while(b[m]) m++;
p1=1;
p2=1;
for(i=0; i<n; i++)
{
v1=(v1*58+(a[i]-'A'))%1000117;
v2=(v2*58+(a[i]-'A'))%100109;
p1=(p1*58)%1000117;
p2=(p2*58)%100109;
}
for(i=0; i<n; i++)
{
w1=(w1*58+(b[i]-'A'))%1000117;
w2=(w2*58+(b[i]-'A'))%100109;
}
if(v1==w1&&v2==w2)
{
k++;
q[k]=0;
}
for(i=n; i<m; i++)
{
w1=(w1*58-p1*(b[i-n]-'A')+(b[i]-'A')+1000234013689)%1000117;
w2=(w2*58-p2*(b[i-n]-'A')+(b[i]-'A')+10021811881)%100109;
if(v1==w1&&v2==w2)
{
k++;
q[k]=i+1-n;
}
}
g<<k<<'\n';
for(i=1; i<=k; i++)
{
g<<q[i]<<" ";
}
g<<'\n';
f.close(); g.close();
return 0;
}