Pagini recente » Cod sursa (job #717754) | Cod sursa (job #1632095) | Cod sursa (job #2564143) | Cod sursa (job #2406765) | Cod sursa (job #3126163)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
long long MOD1=1000000007, MOD2=1000000009, x, y, a, b, p1=1, p2=1, r[2000005], nr, i, n, m;
int main()
{
fin>>s2>>s1;
m=s2.size();
n=s1.size();
for (i=0; i<m; i++) {
x=(127*x+(s2[i]-'0'+1))%MOD1;
y=(127*y+(s2[i]-'0'+1))%MOD2;
if (i!=0) {p1=(p1*127)%MOD1; p2=(p2*127)%MOD2;}
}
for (i=0; i<m; i++) {
a=(127*a+(s1[i]-'0'+1))%MOD1;
b=(127*b+(s1[i]-'0'+1))%MOD2;
}
if (x==a && y==b) {
r[++nr]=0;
}
for (i=m; i<n; i++) {
a=(((MOD1+a-((s1[i-m]-'0'+1)*p1)%MOD1)%MOD1)*127+(s1[i]-'0'+1))%MOD1;
b=(((MOD2+b-((s1[i-m]-'0'+1)*p2)%MOD2)%MOD2)*127+(s1[i]-'0'+1))%MOD2;
if (x==a && y==b) r[++nr]=i-m+1;
}
fout<<nr<<'\n';
for (i=1; i<=min(nr, 1000ll); i++) {
fout<<r[i]<<' ';
}
return 0;
}