Pagini recente » Cod sursa (job #2280387) | Rating Mihai Stoica (Mihai21) | Cod sursa (job #79725) | Cod sursa (job #215964) | Cod sursa (job #1464853)
#include<fstream>
#include<cstring>
#define p 97
#define mod1 1000003
#define mod2 1000007
using namespace std;
int n, m, i, h1, h2, s1, s2, nr, pt1, pt2;
char a[2000005], b[2000005];
int v[1005];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
fin>> (a + 1);
n = strlen(a + 1);
for(i = 1; i <= n; i++){
s1 = (s1 * p + a[i]) % mod1;
s2 = (s2 * p + a[i]) % mod2;
}
pt1 = pt2 = 1;
for(i = 1; i < n; i++){
pt1 = pt1 * p % mod1;
pt2 = pt2 * p % mod2;
}
fin>> (b + 1);
m = strlen(b + 1);
for(i = 1; i <= m; i++){
h1 = (h1 * p + b[i]) % mod1;
h2 = (h2 * p + b[i]) % mod2;
if(i >= n){
if(h1 == s1 && h2 == s2){
nr++;
if(nr <= 1000){
v[nr] = i - n;
}
}
h1 -= pt1 * b[i - n + 1] % mod1;
if(h1 < 0){
h1 += mod1;
}
h2 -= pt2 * b[i - n + 1] % mod2;
if(h2 < 0){
h2 += mod1;
}
}
}
fout<< nr <<"\n";
for(i = 1; i <= min(nr, 1000); i++){
fout<< v[i] <<" ";
}
return 0;
}