Pagini recente » Cod sursa (job #2953928) | Cod sursa (job #61898) | Cod sursa (job #3283380) | Cod sursa (job #473579) | Cod sursa (job #1862521)
#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];
}
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];
}
if (b[i] == a[j]) {
j++;
}
if (a[j] == '\0') {
indices.push_back(i - pattern_length);
j = prev_pos[j - 1];
}
}
fout << indices.size() << "\n";
for (i = 0; i < indices.size(); i++) {
fout << indices[i] << " ";
}
return 0;
}