Pagini recente » Cod sursa (job #2510055) | Cod sursa (job #1382094) | Cod sursa (job #1178184) | Cod sursa (job #1810807) | Cod sursa (job #3250246)
#include <bits/stdc++.h>
#define H1 1000000007
#define H2 1000000009
#define C 127
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
long long n, m, x1=1, x2=1, a1, a2, b1, b2, k;
long long 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++) {
cout<<b1<<' '<<(b[i-n]-'0')*x1<<' ';
b1=(b1-((b[i-n]-'0')*x1))%H1;
b1=(b1*C+b[i]-'0')%H1;
b2=(b2-((b[i-n]-'0')*x2))%H2;
b2=(b2*C+b[i]-'0')%H2;
if (i==7) cout<<b1<<'\n'<<b2;
if (b1==a1 && b2==a2) {
v[++k]=i+1-n;
if (k>=1000) break;
}
}
fout<<k<<'\n';
for (i=1; i<=k; i++) {
fout<<v[i]<<' ';
}
return 0;
}