Pagini recente » Cod sursa (job #1540210) | Cod sursa (job #1469624) | Cod sursa (job #1282269) | Cod sursa (job #2522514) | Cod sursa (job #873088)
Cod sursa(job #873088)
#include <stdio.h>
#include <string.h>
using namespace std;
//Constante
const int sz = (int)2e6 + 1;
const int mod1 = 20007;
const int mod2 = 20021;
const int P = 73;
//Variabile
FILE *in,*out;
char sub[sz], str[sz];
int subHash1, subHash2;
int strHash1, strHash2;
int P1=1, P2=1;
int answer;
int answers[1001];
int main()
{
in=fopen("strmatch.in","rt");
out=fopen("strmatch.out","wt");
fscanf(in,"%s",sub);
fscanf(in,"%s",str);
int subLen = strlen(sub);
int strLen = strlen(str);
subHash1 = subHash2 = (int)sub[0];
strHash1 = strHash2 = (int)str[0];
for(int i=1; i<subLen; ++i)
{
subHash1 = (subHash1 * P + sub[i]) % mod1;
subHash2 = (subHash2 * P + sub[i]) % mod2;
strHash1 = (strHash1 * P + str[i]) % mod1;
strHash2 = (strHash2 * P + str[i]) % mod2;
P1 = (P1*P) % mod1;
P2 = (P2*P) % mod2;
}
if(subHash1 == strHash1 && subHash2 == strHash2)
{
++answer;
// if(answer <= 1000)
// answers[answer] = 0;
}
for(int i=subLen; i<strLen; ++i)
{
strHash1 = ((strHash1 - str[i-subLen]*P1) % mod1) + mod1;
strHash1 = (strHash1*P + str[i]) % mod1;
strHash2 = ((strHash2 - str[i-subLen]*P2) % mod2) + mod2;
strHash2 = (strHash2*P + str[i]) % mod2;
if(subHash1 == strHash1 && subHash2 == strHash2)
{
++answer;
if(answer <= 1000)
answers[answer] = i-subLen+1;
}
}
fprintf(out, "%d\n",answer);
if(answer <= 1000)
for(int i=1; i<=answer; ++i)
fprintf(out,"%d ",answers[i]);
else
for(int i=1; i<=1000; ++i)
fprintf(out,"%d ", answers[i]);
fclose(in);
fclose(out);
return 0;
}