Pagini recente » Cod sursa (job #2556836) | Cod sursa (job #2847352) | Cod sursa (job #1075907) | simulare_oji_2023_clasa_10_17_martie | Cod sursa (job #1460215)
#include <bits/stdc++.h>
using namespace std;
#define B 9901
#define MAXN 2000005
int64_t Part[MAXN], Pow[MAXN];
char t[MAXN], p[MAXN];
int64_t getHash(int e, int l) {
return Part[e] - Part[e-l] * Pow[l];
}
int Sol[1005];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin>>p;
cin>>t+1;
t[0] = '#';
Pow[0] = 1;
for(int i=1; t[i]; i++) {
Part[i] = Part[i-1] * B + t[i];
Pow[i] = Pow[i-1] * B;
}
int64_t h = 0;
int l;
for(l=0; p[l]; l++) {
h = h * B + p[l];
}
int64_t nr = 0;
for(int i=l; t[i]; i++) {
if(getHash(i, l) == h) {
nr++;
if(nr <= 1000)
Sol[nr] = i-l;
}
}
cout<<nr<<'\n';
for(int i=1; i<=nr && i <= 1000; i++) {
cout<<Sol[i]<<" ";
}
return 0;
}