Pagini recente » Cod sursa (job #1293732) | Cod sursa (job #394178) | Cod sursa (job #228784) | Cod sursa (job #648308) | Cod sursa (job #3333426)
#include <stdio.h>
#define MAX_SECV_N 2000000
#define BAZA 91514629
#define MOD 91511197
char a[MAX_SECV_N], b[MAX_SECV_N];
unsigned long long aenc[MAX_SECV_N], benc=0;
unsigned long long BAZAlam;
int pos[1000];
unsigned long long fastexp(unsigned long long b, int p) {
if(p==0)
return 1;
unsigned long long y = fastexp(b, p/2);
y = (y*y)%MOD;
if(p%2==1)
y = (y*b)%MOD;
return y;
}
int main()
{
//FILE *fin = fopen("D:/GitHub_Repos/AlgoArchive/Algo_v2/InfoArena/PotrivireaSirurilor/strmatch.in", "r");
//FILE *fout = fopen("D:/GitHub_Repos/AlgoArchive/Algo_v2/InfoArena/PotrivireaSirurilor/strmatch.out", "w");
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int n=0, m=0, i, j, p=0;
unsigned long long xfinal, x1, x2;
char ch, val;
ch = fgetc(fin);
while(ch!='\n') {
b[m] = ch;
m++;
ch = fgetc(fin);
}
BAZAlam = fastexp(BAZA, m);
ch = fgetc(fin);
while(ch!=EOF && ch!='\n') {
a[n] = ch;
n++;
ch = fgetc(fin);
}
for(i=0; i<m; i++) {
if('a'<=b[i]&&b[i]<='z')
val = b[i]-'a';
else
val = b[i]-'A'+26;
benc = (benc*BAZA+val)%MOD;
}
if('a'<=a[0]&&a[0]<='z')
aenc[0] = a[0]-'a';
else
aenc[0] = a[0]-'A'+26;
for(i=1; i<n; i++) {
if('a'<=a[i]&&a[i]<='z')
val = a[i]-'a';
else
val = a[i]-'A'+26;
aenc[i] = (aenc[i-1]*BAZA+val)%MOD;
}
for(i=0; i<=n-m; i++) {
x1 = aenc[i+m-1];
if(i==0)
x2 = 0;
else
x2 = (aenc[i-1]*BAZAlam)%MOD;
xfinal = (x1-x2+MOD)%MOD;
if(xfinal == benc) {
j=0;
while(j<m && b[j]==a[i+j])
j++;
if(j==m) {
if(p<1000)
pos[p] = i;
p++;
}
}
}
fprintf(fout, "%d\n", p);
for(i=0; i<1000; i++)
fprintf(fout, "%d ", pos[i]);
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}