Pagini recente » Cod sursa (job #1707263) | Cod sursa (job #1940109) | Cod sursa (job #3224542) | Cod sursa (job #1723955) | Cod sursa (job #3291650)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p=127;
const int mod1=666013;
const int mod2=10005;
int k, sol[2000005];
string a, b;
int main()
{
fin >> a >> b;
int n=a.size();
int m=b.size();
if (n>m)
{
fout << 0;
return 0;
}
int p1=1, p2=1;
int h1=0, h2=0;
for (int i=0; i<n; i++)
{
h1=(h1*p+a[i])%mod1;
h2=(h2*p+a[i])%mod2;
if (i!=0)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
int v1=0, v2=0;
for (int i=0; i<n; i++)
{
v1=(v1*p+b[i])%mod1;
v2=(v2*p+b[i])%mod2;
}
if (v1==h1 && v2==h2)
sol[++k]=0;
for (int i=n; i<m; i++)
{
v1=((v1-(b[i-n]*p1)%mod1+mod1)*p+b[i])%mod1;
v2=((v2-(b[i-n]*p2)%mod2+mod2)*p+b[i])%mod2;
if (v1==h1 && v2==h2)
sol[++k]=i-n+1;
}
fout << k << '\n';
for (int i=1; i<=min(k,1000); i++)
fout << sol[i] << " ";
return 0;
}