Pagini recente » Cod sursa (job #1294410) | Cod sursa (job #2321347) | Cod sursa (job #984490) | Cod sursa (job #1806641) | Cod sursa (job #2721085)
#include <fstream>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
char a[2000001];
char b[2000001];
int table[2000001];
int lA, lB;
vector<int> ind;
void read() {
ifstream f("strmatch.in");
f.getline(a, 2000001);
f.getline(b, 2000001);
f.close();
}
void solve() {
int i = 0, j = 1;
lA = strlen(a);
lB = strlen(b);
while (j < lA) {
if (a[i] == a[j]) {
table[j] = i + 1;
i++, j++;
}
else if (i != 0)
i = table[i - 1];
else j++;
}
j = 0;
for (i = 0; i < lB;) {
if (b[i] == a[j])
i++, j++;
else if (j != 0)
j = table[j - 1];
else i++;
if (j == lA) {
ind.emplace_back(i - j);
j = table[j - 1];
}
}
}
void output() {
ofstream g("strmatch.out");
int nr, i;
g << ind.size() << '\n';
if (ind.size() > 1000)
nr = 1000;
else nr = ind.size();
for (i = 0; i < nr; i++)
g << ind[i] << ' ' ;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}