Pagini recente » Cod sursa (job #887211) | Cod sursa (job #294349) | Cod sursa (job #2693588) | Cod sursa (job #1913376) | Cod sursa (job #1366713)
#include <stdio.h>
#include <string.h>
const int MAX = 2000001;
const int MOD = 1000003;
const int BASE = 73;
char str[MAX], substr[MAX];
int strLen, substrLen;
int matches[1001];
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);
strLen = strlen(str);
substrLen = strlen(substr);
long int substrHash = substr[0];
int pow = 1;
for (int i = 1; i < substrLen; i++) {
pow *= BASE;
substrHash = (substrHash * BASE + substr[i]) % MOD;
}
// ---
long int candidateHash = 0;
for (int i = 0; i < substrLen; i++) {
candidateHash = (candidateHash * BASE + str[i]) % MOD;
}
if (candidateHash == substrHash) {
match(0);
}
// ---
for (int i = 0, j = substrLen; j < strLen && nMatches < 1000; i++, j++) {
char back = str[i];
char front = str[j];
candidateHash = ((candidateHash - (back * pow) % MOD + MOD) * BASE + front) % MOD;
if (candidateHash == substrHash) {
match(i + 1);
}
}
// ---
printf("%d\n", nMatches);
for (int i = 0; i < nMatches && i < 1000; i++) {
printf("%d ", matches[i]);
}
fclose(fin);
fclose(fout);
return 0;
}