Pagini recente » Istoria paginii runda/the_dolphin_project/clasament | Istoria paginii runda/iconcurs10 | Istoria paginii runda/stalpi2 | Profilu' lu' Razvan | Cod sursa (job #2241330)
#include<bits/stdc++.h>
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1 = 100007;
const int MOD2 = 100021;
const int P = 73;
string a,b;
int ha1,ha2, h1,h2, d1=1,d2=1, rs;
bool u[NMAX];
int32_t main() {
ios_base::sync_with_stdio(false); fin.tie(NULL);
fin>>a>>b;
int sa = a.size(), sb=b.size();
if (sa>sb) return fout<<0,0;
for (int i=0; i<sa; i++) {
ha1 = (ha1*P + a[i])%MOD1;
ha2 = (ha2*P + a[i])%MOD2;
h1 = (h1*P + b[i])%MOD1;
h2 = (h2*P + b[i])%MOD2;
if (i != 0) {
d1 = (d1*P)%MOD1;
d2 = (d2*P)%MOD2;
}
}
if (h1==ha1 && h2==ha2) ++rs, u[0]=1;
for (int i=sa; i<sb; i++) {
h1 = ((h1 - (b[i - sa]*d1)%MOD1 + MOD1)*P + b[i])%MOD1;
h2 = ((h2 - (b[i - sa]*d2)%MOD2 + MOD2)*P + b[i])%MOD2;
if (h1 == ha1 && h2 == ha2) {
rs++;
u[i-sa+1]=1;
}
}
fout<<rs<<'\n'; rs=1000;
for (int i=0; i<sb && rs; i++) {
if (u[i]) {
fout<<i<<" "; rs--;
}
}
return 0;
}