Pagini recente » Cod sursa (job #2313012) | Cod sursa (job #1116510) | Cod sursa (job #209094) | Cod sursa (job #1487437) | Cod sursa (job #632519)
Cod sursa(job #632519)
#include<cstdio>
#include<string.h>
#define N 2000005
#define MOD 1299709
#define BASE 62
char sir[260];
int contor;
char a[N];
int result[1005];
char b[N];
int ok;
long long t;
int NA, NB;
int powb;
long long str;
int modulus(int a, int b) {
if(a < 0) return b - modulus(-a, b);
int cat = a / b;
return a - b * cat;
}
void init() {
powb = 1;
for(int i = 1; i < NA; i++)
powb = modulus((powb * BASE), MOD);
for(char i = 'A'; i <= 'Z'; i++)
sir[i] = i - 'A';
for(char i = 'a'; i <= 'z'; i++)
sir[i] = i - 'a' + 26;
for(char i = '0'; i <= '9'; i++)
sir[i] = i - '0' + 52;
return;
}
int minim(int a, int b) {
if(a < b) return a;
return b;
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
NA = strlen(a);
NB = strlen(b);
init();
for(int i = 0; i < NA; i++) {
t = modulus(modulus((t * BASE), MOD) + sir[a[i]], MOD);
str = modulus(modulus((str * BASE), MOD) + sir[b[i]], MOD);
}
for(int i = 1; i <= NB - NA + 1; i++) {
str = modulus(modulus(modulus((str - modulus(powb * sir[b[i-1]],MOD)), MOD) * BASE,MOD) + sir[b[i + NA - 1]], MOD);
if(str == t) {
ok = 1;
for(int j = i; j < i + NA; j++)
if(b[j] != a[j - i]) ok = 0;
if(ok == 1) {
contor++;
if (contor <= 1000)
result[contor] = i;
}
}
}
printf("%d\n",contor);
for(int i = 1; i <= minim(contor, 1000); i++)
printf("%d ", result[i]);
return 0;
}