Pagini recente » Cod sursa (job #879665) | Cod sursa (job #1712012) | Cod sursa (job #1578652) | Cod sursa (job #1168732) | Cod sursa (job #2059173)
#include<cstdio>
#include<cstring>
#define MAX_LEN 2000000
#define MAX_POS 1000
#define MOD 24019
#define d 256
using namespace std;
char T[MAX_LEN+1], P[MAX_LEN+1];
int pos[MAX_POS], hashT, hashP, h, k, n, m;
int main() {
int i, j, l;
bool ok;
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);
h = 1;
for(i=0; i<m; i++) {
hashT = (d*hashT + T[i]) % MOD;
hashP = (d*hashP + P[i]) % MOD;
if(i != m - 1)
h = (d*h) % MOD;
}
for(i=0; i<=n-m; i++) {
if(hashT == hashP) {
ok = true;
for(j=0; j<m && ok; j++)
if(T[i+j] != P[j])
ok = false;
if(ok) {
if(k < MAX_POS)
pos[k++] = i;
else k++;
}
}
if(i < n - m) {
hashT = (d*(hashT - T[i]*h) + T[i+m]) % MOD;
if(hashT < 0)
hashT = (hashT + MOD);
}
}
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;
}