Pagini recente » Cod sursa (job #1182740) | Cod sursa (job #1285536) | Cod sursa (job #785067) | Cod sursa (job #2706075) | Cod sursa (job #2907764)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr = 1e9;
int mod[2] = {nr + 7,nr + 9};
int h[2],h2[2],p[2] = {1,1};
char v[2000000];
char v2[2000000];
int ans[1000],cnt = 0;
void add(int a){
if(cnt < 1000){
ans[cnt] = a;
}
cnt++;
}
int main()
{
int n = 0,i,m = 0,j;
v[n++] = fin.get();
while(v[n - 1] != '\n'){
v[n++] = fin.get();
};
n--;
v2[m++] = fin.get();
while(v2[m - 1] != '\n'){
v2[m++] = fin.get();
};
m--;
for(i = 0;i < n;i++){
for(j = 0;j < 2;j++){
h[j] = (1ll*h[j]*256 + v[i])%mod[j];
h2[j] = (1ll*h2[j]*256 + v2[i])%mod[j];
p[j] = 1ll*p[j]*256%mod[j];
}
}
for(i = n;i < m;i++){
///check equality
j = 0;
while(j < 2 && h[j] == h2[j]){
j++;
}
if(j == 2){
add(i - n);
}
///add v2[i]
for(j = 0;j < 2;j++){
h2[j] = (1ll*h2[j]*256 + v2[i])%mod[j];
///remove v2[i - n]
h2[j] = (0ll + h2[j] - 1ll*(v2[i - n])*p[j])%mod[j];
if(h2[j] < 0)h2[j]+=mod[j];
}
}
j = 0;
while(j < 2 && h[j] == h2[j]){
j++;
}
if(j == 2){
add(i - n);
}
fout<<cnt<<'\n';
for(i = 0;i < min(cnt,1000);i++){
fout<<ans[i]<<' ';
}
return 0;
}