Pagini recente » Cod sursa (job #1205857) | Cod sursa (job #1720496) | Cod sursa (job #2246788) | Cod sursa (job #936671) | Cod sursa (job #1455619)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAX 2000000
int *computePi (char *s) {
int l = strlen(s);
int *pi = new int[l];
pi[0] = 0;
int k = 0;
for (int i = 1; i < l; ++i) {
while (k > 0 && s[i] != s[k]) {
k = pi[k];
}
if (s[i] == s[k]) ++k;
pi[i] = k;
}
return pi;
}
int strMatch (char *target, char *source, vector <int> & v) {
int *pi = computePi(target);
int lt = strlen(target), ls = strlen(source), k = 0, matchesNo = 0;
for (int i = 0; i < ls; ++i) {
while (k > 0 && target[k] != source[i]) {
k = pi[k];
}
if (target[k] == source[i]) ++k;
if (k == lt) {
++matchesNo;
v.push_back(i - lt + 1);
k = pi[k-1];
}
}
delete[] pi;
return matchesNo;
}
int main (void) {
FILE *in = fopen("strmatch.in", "r");
char *buffer = new char[MAX];
fgets(buffer, MAX, in);
buffer[strlen(buffer) - 1] = '\0';
char *s1 = strdup(buffer);
fgets(buffer, MAX, in);
buffer[strlen(buffer) - 1] = '\0';
char *s2 = strdup(buffer);
delete[] buffer;
fclose(in);
FILE *out = fopen("strmatch.out", "w");
vector <int> v;
int matchesNo = strMatch(s1, s2, v);
fprintf(out, "%d\n", matchesNo);
for (int i = 0; i < matchesNo && i < 2000; ++i) {
fprintf(out, "%d ", v[i]);
}
delete[] s1;
delete[] s2;
v.clear();
fclose(out);
return 0;
}