Pagini recente » Cod sursa (job #1421883) | Cod sursa (job #25228) | Cod sursa (job #3257395) | Cod sursa (job #714623) | Cod sursa (job #1889758)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
const int N = 2000010;
string a, b;
// both tables are 0-indexed
int bcr[26], gsr[N], f[N], n, m;
void build_bcd() {
for (int i = 0; i < n; ++i) {
bcr[a[i] - int('A')] = i;
}
}
void build_gsr() {
// f[i] = biggest suffix that matches over the end of the array
f[n] = n + 1;
int k = n;
for (int i = n - 1; i >= 0; --i) {
//cerr << i << ' ' << k << '\n';
while (a[i] != a[k] && k < n) {
//cerr << k << '\n';
// update the shifts while i move
if (gsr[k] == 0) {
gsr[k] = k - i;
}
// move to right like at KMP
k = f[k + 1] - 1;
//break;
}
f[i] = k;
--k;
}
// the other case is matching on the beginning of the array
// the values is f[0]; if i arrive at the place of f[0], the values should
// decrease as I am maching the smallest part of array
k = f[0];
for (int i = 0; i <= m; ++i) {
// this stuff for all cause we want to align the things
if (gsr[i] == 0) {
gsr[i] = k;
}
if (i == k) {
// the rightmost thing is this one, not the other one
k = f[k];
}
}
}
int main() {
F >> a >> b;
n = a.size();
m = b.size();
build_bcd();
build_gsr();
int i = 0, k = 0;
int ans = 0;
vector<int> v;
while (i <= m - n) {
//cout << i << '\n';
k = n - 1;
while (k >= 0 && a[k] == b[i + k]) {
k--;
}
if (k < 0) {
ans ++;
v.push_back(i);
i += gsr[0];
}
else
i += max(gsr[k + 1], k - bcr[b[i + k] - int('A')] + 1);
}
G << ans << '\n';
for (auto x : v) {
G << x << ' ';
}
G << '\n';
}