Pagini recente » Cod sursa (job #3225132) | Cod sursa (job #1174411) | Cod sursa (job #1675215) | Cod sursa (job #769459) | Cod sursa (job #1367617)
#include <stdio.h>
#include <string.h>
const int MAX = 2000001;
const int MOD1 = 100007; // 3367900313; // 1299827; // 1000003;
const int MOD2 = 100021;
const int BASE = 73;
char str[MAX], substr[MAX];
int matches[MAX];
int nMatches;
void match (int position) {
matches[nMatches] = position;
nMatches++;
}
int main () {
FILE *fin = freopen("strmatch.in", "rt", stdin);
FILE *fout = freopen("strmatch.out", "wt", stdout);
scanf("%s %s", substr, str);
int substrLen = strlen(substr);
int strLen = strlen(str);
// ---
int substrHash1 = substr[0];
int substrHash2 = substr[0];
int pow1 = 1;
int pow2 = 1;
for (int i = 1; i < substrLen; i++) {
char front = substr[i];
pow1 = (pow1 * BASE) % MOD1;
pow2 = (pow2 * BASE) % MOD2;
substrHash1 = (substrHash1 * BASE + front) % MOD1;
substrHash2 = (substrHash2 * BASE + front) % MOD2;
}
//printf("pow %ld\n", pow);
//printf("substrHash %ld\n", substrHash);
// ---
int candidateHash1 = 0;
int candidateHash2 = 0;
for (int i = 0; i < substrLen; i++) {
char front = str[i];
candidateHash1 = (candidateHash1 * BASE + front) % MOD1;
candidateHash2 = (candidateHash2 * BASE + front) % MOD2;
}
if (candidateHash1 == substrHash1 && candidateHash2 == substrHash2) {
match(0);
}
// ---
for (int i = 0, j = substrLen; j < strLen; i++, j++) {
char back = str[i];
char front = str[j];
candidateHash1 = ((candidateHash1 - (back * pow1) % MOD1 + MOD1) * BASE + front) % MOD1;
candidateHash2 = ((candidateHash2 - (back * pow2) % MOD2 + MOD2) * BASE + front) % MOD2;
//printf("candidateHash %ld substringHash %ld\n", candidateHash, substrHash);
if (candidateHash1 == substrHash1 && candidateHash2 == substrHash2) {
match(i + 1);
}
}
// ---
printf("%d\n", nMatches);
for (int i = 0; i < nMatches && i < 1000; i++) {
printf("%d ", matches[i]);
}
printf("\n");
fclose(fin);
fclose(fout);
return 0;
}