Pagini recente » Cod sursa (job #666805) | Cod sursa (job #2239947) | Cod sursa (job #997193) | Cod sursa (job #2078958) | Cod sursa (job #3231660)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p=27;
const int MOD1=666013;
const int MOD2=10003;
int k, sol[2000005];
string a, b;
int main()
{
fin >> a >> b;
int n=a.size();
int m=b.size();
int p1=0, p2=0;
int h1=0, h2=0;
for (int i=0; i<n; i++)
{
h1=(h1*p+a[i])%MOD1;
h2=(h2*p+a[i])%MOD2;
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';
sort(sol+1,sol+k+1);
for (int i=1; i<=k; i++)
fout << sol[i];
return 0;
}