Pagini recente » Cod sursa (job #1341605) | Borderou de evaluare (job #2773670) | Cod sursa (job #870587) | Cod sursa (job #899822) | Cod sursa (job #2240905)
#include<bits/stdc++.h>
#define int long long
#define NMAX 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout(" strmatch.out");
const int m = 100007;
const int p = 43;
string a,b;
int ha, h1, d=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++) {
ha = (ha*p + a[i])%m;
h1 = (h1*p + b[i])%m;
if (i != 0) {
d = (d*p)%m;
}
}
if (h1==ha) ++rs, u[0]=1;
for (int i=sa; i<sb; i++) {
h1 = ((((h1 - (b[i - sa]*d)%m + m)%m)*p) + b[i])%m;
if (h1 == ha) {
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;
}