Pagini recente » Cod sursa (job #739638) | Cod sursa (job #622337) | Cod sursa (job #21066) | Cod sursa (job #2657656) | Cod sursa (job #1455645)
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define MAX 2000005
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 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) ++k;
pi[i] = k;
}
return pi;
}
int strMatch (char *target, char *source, int *v) {
int *pi = computePi(target);
int lt = strlen(target), ls = strlen(source), k = 0, matchesNo = 0;
/*for (int i = 0; i < lt; ++i) {
printf("%d ", pi[i]);
}
printf("\n");
*/
for (int i = 0; i < ls && matchesNo <= 1000; ++i) {
while (k && target[k] != source[i]) {
k = pi[k - 1];
}
if (target[k] == source[i]) ++k;
if (k == lt) {
v[matchesNo] = i - lt + 1;
++matchesNo;
k = pi[k - 1];
}
}
delete[] pi;
return matchesNo;
}
int main (void) {
FILE *f = fopen("strmatch.in", "r");
char *buffer = new char[MAX];
fgets(buffer, MAX, f);
buffer[strlen(buffer) - 1] = '\0';
char *s1 = strdup(buffer);
fgets(buffer, MAX, f);
buffer[strlen(buffer) - 1] = '\0';
char *s2 = strdup(buffer);
delete[] buffer;
freopen("strmatch.out", "w", f);
int *v = new int[1000];
int matchesNo = strMatch(s1, s2, v);
fprintf(f, "%d\n", matchesNo);
for (int i = 0; i < matchesNo; ++i) {
fprintf(f, "%d ", v[i]);
}
delete[] s1;
delete[] s2;
delete[] v;
fclose(f);
return 0;
}