Pagini recente » Cod sursa (job #585207) | Cod sursa (job #575231) | Cod sursa (job #1677773) | Cod sursa (job #1073021) | Cod sursa (job #2592423)
#include <fstream>
#include <cstring>
#define PRIM 699967
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 putere, hash1, hash2, val;
int main()
{
fin >> M >> N;
putere = 1;
n = strlen(N);
m = strlen(M);
hash1 = 0;
for(i = 0; i<m; i++){
hash1 = (hash1 * 29 + M[i]-'A') % PRIM;
putere *= 29;
}
hash2 = 0;
for(i = 0; i<=m-1; i++){
hash2 = (hash2 * 29 + N[i]-'A') % PRIM;
}
if(hash1 == hash2){
valori++;
p[valori] = 0;
}
for(i = 1; i<=n-m && valori <= 1000; i++){
hash2 = ((hash2 - (N[i-1]-'A')*(putere/29)) * 29 + N[i+m-1]-'A') % PRIM;
if(hash1 == hash2){
valori++;
p[valori] = i;
}
}
fout << valori % 1000 << '\n';
for(i = 1; i<=valori; i++){
fout << p[i] << ' ';
}
return 0;
}