Pagini recente » Diferente pentru schimbare-borland/alternativa intre reviziile 3 si 2 | Cod sursa (job #2427331) | Monitorul de evaluare | Cod sursa (job #1513259) | Cod sursa (job #1839495)
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <string.h>
#define NMAX 2000000
#define MAXSIZE 1000
using namespace std;
vector<int> BuildTempArray(char s[]) {
int i = 1;
int j = 0;
int n = strlen(s);
vector<int> temp_array;
temp_array.push_back(0);
while (i < n) {
if (s[i] == s[j]) {
temp_array.push_back(temp_array[j] + 1);
++ i; ++j;
} else {
if (j) {
j = temp_array[j - 1];
} else {
temp_array.push_back(0);
++ i;
}
}
}
return temp_array;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char A[NMAX], B[NMAX];
scanf("%s", A);
scanf("%s", B);
vector<int> temp_array = BuildTempArray(A);
// for (int i = 0; i < temp_array.size(); ++ i) {
// printf("%d ", temp_array[i]);
// }
vector<int> matches;
int j = 0;
int N = strlen(B);
bool should_stop = false;
for (int i = 0; i < N && !should_stop; ++ i) {
while (j != 0 && A[j] != B[i] && !should_stop) {
j = temp_array[j - 1];
}
if (B[i] == A[j]) {
++ j;
}
if (j == strlen(A)) {
j = temp_array[j - 1];
matches.push_back(i - j - 2);
if (matches.size() == MAXSIZE) {
should_stop = true;
}
}
}
printf("%d\n", (int)matches.size());
for (int i = 0; i < matches.size(); ++ i) {
printf("%d ", matches[i]);
}
printf("\n");
return 0;
}