Pagini recente » Cod sursa (job #284412) | Cod sursa (job #573543) | Cod sursa (job #1254142) | Cod sursa (job #2326652) | Cod sursa (job #2207702)
#include<cstdio>
#include<cstring>
#define MAX_LEN 2000000
#define MAX_POS 1000
#define MOD1 24019
#define MOD2 27319
#define d 256
using namespace std;
char T[MAX_LEN+1], P[MAX_LEN+1];
int pos[MAX_POS], n, m, hashT1, hashT2, hashP1, hashP2, h1, h2, k;
int main() {
int i;
FILE *fin, *fout;
fin = fopen("strmatch.in","r");
fout = fopen("strmatch.out","w");
fscanf(fin,"%s%s",P,T);
n = strlen(T);
m = strlen(P);
h1 = h2 = 1;
for(i = 0; i < m; i++) {
hashT1 = (hashT1*d + T[i]) % MOD1;
hashT2 = (hashT2*d + T[i]) % MOD2;
hashP1 = (hashP1*d + P[i]) % MOD1;
hashP2 = (hashP2*d + P[i]) % MOD2;
if(i != m - 1) {
h1 = (h1*d) % MOD1;
h2 = (h2*d) % MOD2;
}
}
for(i = 0; i <= n - m; i++) {
if(hashT1 == hashP1 && hashT2 == hashP2) {
if(k < MAX_POS)
pos[k++] = i;
else k++;
}
if(i < n - m) {
hashT1 = (d*(hashT1 - T[i]*h1) + T[i+m]) % MOD1;
hashT2 = (d*(hashT2 - T[i]*h2) + T[i+m]) % MOD2;
if(hashT1 < 0)
hashT1 += MOD1;
if(hashT2 < 0)
hashT2 += MOD2;
}
}
fprintf(fout,"%d\n",k);
if(k > MAX_POS)
k = MAX_POS;
for(i = 0; i < k; i++)
fprintf(fout,"%d ",pos[i]);
fprintf(fout,"\n");
fclose(fin);
fclose(fout);
return 0;
}