Pagini recente » Cod sursa (job #1451830) | Cod sursa (job #2915216) | Cod sursa (job #1395424) | Cod sursa (job #74456) | Cod sursa (job #2259250)
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000005
#define THRESH 1000
using namespace std;
char a[MAX], b[MAX];
int n, m, k, cnt, pi[MAX];
vector<int> res;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> a + 1 >> b + 1;
n = strlen(a + 1);
m = strlen(b + 1);
k = 0;
for (int i = 2; i <= n; ++i) {
while (k && a[i] != a[k + 1])
k = pi[k];
if (a[k + 1] == a[i])
++k;
pi[i] = k;
}
k = 0;
for (int i = 1; i <= m; ++i) {
while (k && b[i] != a[k + 1])
k = pi[k];
if (b[i] == a[k + 1])
++k;
if (k == n) {
++cnt;
if (cnt <= THRESH)
res.push_back(i - n);
}
}
g << cnt << "\n";
for (int i = 0; i < res.size(); ++i)
g << res[i] << " ";
g << "\n";
return 0;
}