Pagini recente » Cod sursa (job #2545162) | Cod sursa (job #2328421) | Cod sursa (job #2597615) | Cod sursa (job #951300) | Cod sursa (job #3231696)
#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];
map <int,bool> mp;
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=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;
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, nr=0; i<=k && nr<=1000; i++)
{
if (!mp[sol[i]])
{
fout << sol[i] << " ";
nr++;
}
mp[sol[i]]=1;
}
return 0;
}