Pagini recente » Cod sursa (job #2540187) | Cod sursa (job #273874) | Cod sursa (job #1729583) | Cod sursa (job #1837479) | Cod sursa (job #1109518)
#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 P=73;
//variabile
char sub[sz],str[sz];
int strLen,subLen;
int subHash1,subHash2;
int strHash1,strHash2;
int answers[1001];
int answer;
int P1=1,P2=1;
int main(void)
{
in=fopen("strmatch.in","rt");
out=fopen("strmatch.out","wt");
fscanf(in,"%s",sub);
fscanf(in,"%s",str);
subLen=strlen(sub);
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;
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(strHash1==subHash1 && strHash2==subHash2)
{
++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;
}