Pagini recente » Cod sursa (job #2152311) | Cod sursa (job #85062) | Cod sursa (job #2739389) | Cod sursa (job #3137081) | Cod sursa (job #2240910)
#include<bits/stdc++.h>
#define int long long
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1 = 100000000091;
const int MOD2 = 1000039;
const int P1 = 103;
const int P2 = 211;
string a,b;
int ha1,ha2, h1,h2, d1=1,d2=1, rs;
bool u[NMAX];
int32_t main() {
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*P1 + a[i])%MOD1;
ha2 = (ha2*P2 + a[i])%MOD2;
h1 = (h1*P1 + b[i])%MOD1;
h2 = (h2*P2 + b[i])%MOD2;
if (i != 0) {
d1 = (d1*P1)%MOD1;
d2 = (d2*P2)%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)%MOD1)*P1) + b[i])%MOD1;
h2 = ((((h2 - (b[i - sa]*d2)%MOD2 + MOD2)%MOD2)*P2) + b[i])%MOD2;
if (h1 == ha1 && h2 == ha2) {
rs++;
u[i-sa+1]=1;
}
}
fout<<rs<<'\n';
for (int i=0; i<sb && rs; i++) {
if (u[i]) {
fout<<i<<" "; rs--;
}
}
return 0;
}