Pagini recente » Cod sursa (job #3226028) | Cod sursa (job #3241063) | Cod sursa (job #94233) | Cod sursa (job #1323351) | Cod sursa (job #1010138)
#include <fstream>
#include <iostream>
#include <vector>
#define MAXN 2000010
using namespace std;
int t[MAXN];
void preprocess(string &w) {
int i = 0, j = -1;
t[i] = j;
while (i < w.size()) {
while (j >= 0 && w[i] != w[j]) j = t[j];
++i; ++j;
t[i] = j;
}
}
vector<int> search(string &w, string &s) {
vector <int> result;
int i = 0, j = -1;
while (i < s.size()) {
while (j >= 0 && s[i] != w[j]) j = t[j];
++i; ++j;
if (j == w.size()) {
result.push_back(i-j);
j = t[j];
}
}
return result;
}
int main() {
string s, w;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> w >> s;
preprocess(w);
vector <int> result = search(w, s);
g << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
g << result[i] << " ";
}
return 0;
}