Pagini recente » Cod sursa (job #1524351) | Cod sursa (job #22130) | Cod sursa (job #434497) | Cod sursa (job #2302548) | Cod sursa (job #1130485)
#include<stdio.h>
#include<string.h>
using namespace std;
FILE *in,*out;
//constante
const int sz=(int) 2e6+1;
const int mod1 = 20007;
const int mod2 = 20021;
const int baza = 73;
//varibile
char str[sz],sub[sz];
int strLen,subLen;
int strHash1,strHash2;
int subHash1,subHash2;
int baza1=1,baza2=1;
int answer;
int answers[1001];
int main(void)
{
in=fopen("strmatch.in","rt");
out=fopen("strmatch.out","wt");
fscanf(in,"%s",sub);
fscanf(in,"%s",str);
strLen = strlen(str);
subLen = strlen(sub);
subHash1 = subHash2 = (int) sub[0];
strHash1 = strHash2 = (int) str[0];
for(int i=1 ; i<subLen ; ++i)
{
subHash1 = (subHash1 * baza + sub[i]) % mod1;
subHash2 = (subHash2 * baza + sub[i]) % mod2;
strHash1 = (strHash1 * baza + str[i]) % mod1;
strHash2 = (strHash2 * baza * str[i]) % mod2;
baza1 = (baza1 * baza) % mod1;
baza2 = (baza2 * baza) % mod2;
}
if(subHash1 == strHash1 && subHash2 == strHash2)
++answer;
for(int i=subLen ; i<strLen ; ++i)
{
strHash1 = ((strHash1 - str[i-subLen] * baza1) % mod1) + mod1;
strHash2 = ((strHash2 - str[i-subLen] * baza2) % mod2) + mod2;
strHash1 = (strHash1 * baza + str[i]) % mod1;
strHash2 = (strHash2 * baza + str[i]) % mod2;
if(subHash1 == strHash1 && subHash2 == strHash2)
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;
}