Pagini recente » Cod sursa (job #2773049) | Cod sursa (job #2440237) | Cod sursa (job #311980) | Cod sursa (job #1511927) | Cod sursa (job #1834994)
#include<iostream>
#include<string.h>
#include<cstdlib>
#include<fstream>
#define NMAX 2000003
using namespace std;
char cuvant[NMAX];
char text[NMAX];
int values[1001];
int *getPrefixes(char w[], int n) {
int *prefix = (int *) calloc (n, sizeof(int));
int i = 1;
int j = 0;
while (i < n) {
if (w[i] == w[j]) {
prefix[i] = j + 1;
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = prefix[j - 1];
}
}
return prefix;
}
int getIndexes(char w[], char s[], int n, int k, int prefix[]) {
int m = 0;
int i = 0;
int count = 0;
while (m < k - n + 1) {
if (i == n) {
//printf("%d ", m);
//cout << s.substr(m, i) << '\n';
values[count++] = m;
m = m + i - prefix[i - 1];
i = prefix[i - 1];
}
if (s[m + i] == w[i]) {
i++;
} else if (i == 0 ){
m = m + 1;
} else {
m = m + i - prefix[i];
i = prefix[i - 1];
}
}
return count;
}
int main() {
int n;
int k;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(cuvant, NMAX, stdin);
fgets(text, NMAX, stdin);
n = strlen(cuvant) - 1;
k = strlen(text) - 1;
int* prefix = getPrefixes(cuvant, n);
/*
for (int i = 0; i < n; i++) {
cout << prefix[i] << ' ';
}
cout << '\n'; */
int count = getIndexes(cuvant, text, n, k, prefix);
cout << count << '\n';
if (count > 1000)
count = 1000;
for (int i = 0; i < count; i++) {
cout << values[i] << ' ';
}
return 0;
}