Pagini recente » Cod sursa (job #289099) | Cod sursa (job #518614) | Cod sursa (job #969018) | Cod sursa (job #2158354) | Cod sursa (job #3250299)
#include <bits/stdc++.h>
#define H1 1000000007
#define H2 1000000009
#define C 80
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
unsigned int n, m, x1=1, x2=1, a1, a2, b1, b2, k;
unsigned int v[2000005], i;
int main()
{
fin>>a>>b;
n=a.size();
m=b.size();
a1=a2=a[0]-'0';
x1=x2=1;
for (i=1; i<n; i++) {
x1*=C, x2*=C;
x1%=H1, x2%=H2;
a1=(a1*C+a[i]-'0')%H1;
a2=(a2*C+a[i]-'0')%H2;
}
b1=b2=b[0]-'0';
for (i=1; i<n; i++) {
b1=(b1*C+b[i]-'0')%H1;
b2=(b2*C+b[i]-'0')%H2;
}
if (a1==b1 && a2==b2) {
v[++k]=0;
}
for (i=n; i<m; i++) {
b1=(b1+H1-((b[i-n]-'0')*x1)%H1)%H1;
b1=(b1*C+b[i]-'0')%H1;
b2=(b2+H2-((b[i-n]-'0')*x2)%H2)%H2;
b2=(b2*C+b[i]-'0')%H2;
if (b1==a1 && b2==a2) {
if (k<=999) {v[++k]=i+1-n;} else {k++;}
}
}
fout<<k<<'\n';
for (i=1; i<=min(int(k), 1000); i++) {
fout<<v[i]<<' ';
}
return 0;
}