Pagini recente » Cod sursa (job #338734) | Cod sursa (job #2158628) | Cod sursa (job #377181) | Cod sursa (job #1109230) | Cod sursa (job #1862544)
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int prev_pos[2000001];
vector<int> indices;
int main() {
fin >> a >> b;
int i, j;
// Precompute positions of where to restart matching in case of a mismatch
for (i = 1, j = 0; a[i] != '\0'; i++) {
if (a[i] == a[j]) {
prev_pos[i] = ++j;
} else {
while (j != 0 && a[i] != a[j]) {
j = prev_pos[j - 1];
}
if (a[i] == a[j]) {
j++;
}
prev_pos[i] = j;
}
}
int pattern_length = strlen(a);
for (i = j = 0; b[i] != '\0'; i++) {
while (j != 0 && b[i] != a[j]) {
j = prev_pos[j - 1];
}
if (b[i] == a[j]) {
j++;
}
if (a[j] == '\0') {
indices.push_back(i - pattern_length + 1);
j = prev_pos[j - 1];
}
}
fout << indices.size() << "\n";
for (i = 0; i < min(1000, (int)indices.size()); i++) {
fout << indices[i] << " ";
}
return 0;
}