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