Pagini recente » Cod sursa (job #3173139) | Cod sursa (job #681788) | Cod sursa (job #1377099) | Cod sursa (job #1261267) | Cod sursa (job #2907780)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr = 1e6;
int mod[2] = {nr + 7,nr + 21};
int h[2],h2[2],p[2] = {1,1};
char v[2000001];
char v2[2000001];
int ans[1001],cnt = 0;
void add(int a){
if(cnt <= 1000){
ans[cnt] = a;
}
cnt++;
}
int main()
{
ios_base::sync_with_stdio(0);
fin.tie(0);
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] = (h[j]*256 + v[i])%mod[j];
h2[j] = (h2[j]*256 + v2[i])%mod[j];
p[j] = p[j]*256%mod[j];
}
}
for(i = n;i < m;i++){
///check equality
if(h[0] == h2[0] && h[1] == h2[1]){
add(i - n);
}
///add v2[i]
for(j = 0;j < 2;j++){
h2[j] = (h2[j]*256 + v2[i] - v2[i - n]*p[j])%mod[j];
if(h2[j] < 0)h2[j]+=mod[j];
}
}
if(h[0] == h2[0] && h[1] == h2[1]){
add(i - n);
}
fout<<cnt<<'\n';
for(i = 0;i < min(cnt,1000);i++){
fout<<ans[i]<<' ';
}
return 0;
}