Pagini recente » Cod sursa (job #1821359) | Cod sursa (job #833042) | Cod sursa (job #138037) | Cod sursa (job #1304613) | Cod sursa (job #2901992)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX_STR 2000000
#define MAX_PATTERN 2000000
#define MAX_MATCHES 1000
char str[MAX_STR];
int strSize;
char pattern[MAX_PATTERN];
int patternSize;
int prefix[MAX_PATTERN];
int matches[MAX_MATCHES];
void computePrefix() {
int i, prefixLen;
prefix[0] = 0;
for (i = 1; i < patternSize; ++i) {
prefixLen = prefix[i - 1];
while (prefixLen && pattern[i] != pattern[prefixLen])
prefixLen = prefix[prefixLen - 1];
if (pattern[i] == pattern[prefixLen])
prefix[i] = prefixLen + 1;
}
}
int main() {
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fscanf(fin, "%s\n%s", pattern, str);
patternSize = strlen(pattern);
strSize = strlen(str);
computePrefix();
int i, j, noMatches;
noMatches = 0;
i = j = 0;
while (i < strSize)
if (str[i] == pattern[j]) {
++i, ++j;
if (j == patternSize) {
if (noMatches < MAX_MATCHES)
matches[noMatches] = i - j;
++noMatches;
j = prefix[j - 1];
}
} else {
if (j > 0)
j = prefix[j - 1];
else
++i;
}
fprintf(fout, "%d\n", noMatches);
noMatches = min(noMatches, MAX_MATCHES);
for (i = 0; i < noMatches; ++i)
fprintf(fout, "%d ", matches[i]);
fclose(fin);
fclose(fout);
return 0;
}