Pagini recente » Cod sursa (job #2854645) | Cod sursa (job #2987568) | Statistici UPB - Todea Mardale Biciila (UPB_Todea_Mardale_Biciila) | Cod sursa (job #1460964) | Cod sursa (job #2902046)
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INVALID_CHAR '$'
#define MAX_STR 2000000
#define MAX_PATTERN 2000000
#define MAX_MATCHES 1000
char str[MAX_STR + MAX_PATTERN + 1];
int patternSize, strSize;
int z[MAX_STR + MAX_PATTERN + 1];
int matches[MAX_MATCHES], noMatches;
void computeZ() {
int i, left, right;
left = right = 0;
for (i = 1; i < strSize; ++i) {
if (i > right) {
left = right = i;
while (right < strSize && str[right - left] == str[right])
++right;
--right;
z[i] = right - left + 1;
} else if (z[i - left] < right - i + 1) {
z[i] = z[i - left];
} else {
left = i;
while (right < strSize && str[right - left] == str[right])
++right;
--right;
z[i] = right - left + 1;
}
}
}
int main() {
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
int i;
fscanf(fin, "%s\n", str);
patternSize = strlen(str);
str[patternSize] = INVALID_CHAR;
fscanf(fin, "%s", str + patternSize + 1);
strSize = strlen(str);
computeZ();
for (i = 0; i < strSize; ++i)
if (z[i] == patternSize) {
if (noMatches < MAX_MATCHES)
matches[noMatches] = i - patternSize - 1;
++noMatches;
}
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;
}