Pagini recente » Cod sursa (job #1175208) | Cod sursa (job #2937844) | Cod sursa (job #2079182) | Cod sursa (job #1149567) | Cod sursa (job #303724)
Cod sursa(job #303724)
#include<cstdio>
#include<cstring>
#define NMAX 2000003
#define mod1 100003
#define mod2 300007
#define base 135
using namespace std;
char A[NMAX],B[NMAX];
int poz[NMAX],e1,e2,hshA1,hshB1,hshA2,hshB2,i,nA,nB,nr;
int main()
{
FILE *f = fopen("strmatch.in","r");
fgets(A,sizeof(A),f);
fgets(B,sizeof(B),f);
fclose(f);
nA = strlen(A);
nB = strlen(B);
A[--nA] = 0;
B[--nB] = 0;
hshA1 = hshA2 = A[0];
hshB1 = hshB2 = B[0];
e1 = e2 = 1;
FILE *g = fopen("strmatch.out","w");
if (nA > nB)
{
fprintf(g,"0\n");
fclose(g);
return 0;
}
for (i = 1; i < nA; ++i)
{
hshA1 = (hshA1 * base + A[i])%mod1;
hshA2 = (hshA2 * base + A[i])%mod2;
hshB1 = (hshB1 * base + B[i])%mod1;
hshB2 = (hshB2 * base + B[i])%mod2;
e1 = (e1 * base) % mod1;
e2 = (e2 * base) % mod2;
}
nr = 0;
if (hshA1 == hshB1 && hshA2 == hshB2)
{
poz[++nr] = 0;
}
for (i = nA; i < nB; ++i)
{
hshB1 = ((hshB1 - (B[i-nA] * e1)%mod1 + mod1) * base + B[i]) % mod1;
hshB2 = ((hshB2 - (B[i-nA] * e2)%mod2 + mod2) * base + B[i]) % mod2;
if (hshA1 == hshB1 && hshA2 == hshB2)
{
poz[++nr] = i-nA+1;
}
}
fprintf(g,"%d\n",nr);
for (i = 1; i <= nr && i <= 1000; ++i)
{
fprintf(g,"%d ",poz[i]);
}
fprintf(g,"\n");
fclose(g);
return 0;
}