Pagini recente » Cod sursa (job #2567935) | Cod sursa (job #2264386) | Cod sursa (job #1658448) | Cod sursa (job #2631476) | Cod sursa (job #1998325)
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX_LEN 2000000
#define MOD1 100007
#define MOD2 100021
#define base 73
#define MAX_POS 1000
char P[MAX_LEN + 1], T[MAX_LEN + 1];
int n, m, k, hashP1, hashP2, hashT1, hashT2, H1, H2;
int pos[MAX_POS];
inline int minim(int x, int y)
{
if(x < y) return x;
return y;
}
int main()
{
int i, nr;
FILE *fin, *fout;
fin = fopen("strmatch.in","r");
fout = fopen("strmatch.out","w");
fscanf(fin,"%s%s",P,T);
m = strlen(P);
n = strlen(T);
H1 = H2 = 1;
for(i=0; i<m; i++)
{
hashP1 = (hashP1 * base + P[i]) % MOD1;
hashP2 = (hashP2 * base + P[i]) % MOD2;
hashT1 = (hashT1 * base + T[i]) % MOD1;
hashT2 = (hashT2 * base + T[i]) % MOD2;
if(i)
{
H1 = (H1 * base) % MOD1;
H2 = (H2 * base) % MOD2;
}
}
for(i=0; i<=n-m; i++)
{
if((hashP1 == hashT1) && (hashP2 == hashT2))
{
if(k < MAX_POS)
pos[k++] = i;
else k++;
}
hashT1 = ((hashT1 - (T[i] * H1) % MOD1 + MOD1) * base + T[i+m]) % MOD1;
hashT2 = ((hashT2 - (T[i] * H2) % MOD2 + MOD2) * base + T[i+m]) % MOD2;
}
nr = minim(k,MAX_POS);
fprintf(fout,"%d\n",k);
for(i=0; i<nr; i++)
fprintf(fout,"%d ",pos[i]);
if(k)
fprintf(fout,"\n");
fclose(fin);
fclose(fout);
return 0;
}