Pagini recente » Cod sursa (job #3194414) | Cod sursa (job #678340) | Stefan Dascalescu | Diferente pentru registru-diplome intre reviziile 42 si 26 | Cod sursa (job #1889764)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
int n, m, p[N];
string a, b;
// p[i] = the length of the longest suffix from position i that overlaps
// over the longest prefix of the array a
int main() {
F >> a >> b;
n = a.size();
m = b.size();
p[1] = 0;
int k = 0; // the current match size
for (int q = 2; q <= n; ++q) {
while (a[q - 1] != a[k] && k > 0) {
k = p[k]; // if the next char does not match, we the first smaller longest
// prefix
}
if (a[q - 1] == a[k]) {
++k;
}
p[q] = k;
}
k = 0;
int ans = 0;
vector<int> v;
for (int q = 1; q <= m; ++q) {
while (b[q - 1] != a[k] && k > 0) {
k = p[k];
}
if (b[q - 1] == a[k]) {
++k;
}
// cout << b[q - 1] << ' ' << k << '\n';
if (k == n) {
++ans;
if (v.size() < 1000) {
v.push_back(q);
}
}
}
G << ans << '\n';
for (auto x : v) {
G << x - n << ' ';
}
G << '\n';
}