Pagini recente » Cod sursa (job #582772) | Cod sursa (job #1487752) | Cod sursa (job #888155) | Cod sursa (job #560628) | Cod sursa (job #2592503)
#include <fstream>
#include <cstring>
#define PRIM1 100007
#define PRIM2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[2000005], M[2000005];
int i, n, m, valori, p[1005];
long long putere1, putere2, hash11, hash12, hash21, hash22, val;
bool prim(int x){
int d;
for(d = 2; d * d <= x && x % d != 0; d++);
return d*d > x ? 1 : 0;
}
int main()
{
fin >> M >> N;
putere1 = putere2 = 1;
n = strlen(N);
m = strlen(M);
hash11 = hash12 = 0;
for(i = 0; i<=m-1; i++){
hash11 = (hash11 * 73 + M[i]) % PRIM1;
hash12 = (hash12 * 73 + M[i]) % PRIM2;
if(i != 0){
putere1 = (putere1 * 73) % PRIM1;
putere2 = (putere2 * 73) % PRIM2;
}
}
hash21 = hash22 = 0;
for(i = 0; i<=m-1; i++){
hash21 = (hash21 * 73 + N[i]) % PRIM1;
hash22 = (hash22 * 73 + N[i]) % PRIM2;
}
if(hash11 == hash21 && hash12 == hash22){
valori++;
p[valori] = 0;
}
int ok = 1;
for(i = 1; i<=n-m && ok; i++){
hash21 = ((hash21 - (N[i-1]*putere1) % PRIM1 + PRIM1) * 73 + N[i+m-1]) % PRIM1;
hash22 = ((hash22 - (N[i-1]*putere2) % PRIM2 + PRIM2) * 73 + N[i+m-1]) % PRIM2;
if(hash11 == hash21 && hash12 == hash22){
valori++;
p[valori] = i;
}
if(valori == 1000){
ok = 1;
}
}
fout << valori << '\n';
for(i = 1; i<=valori; i++){
fout << p[i] << ' ';
}
return 0;
}