Pagini recente » Cod sursa (job #328428) | Cod sursa (job #722816) | Cod sursa (job #892) | Cod sursa (job #764167) | Cod sursa (job #1010141)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#define MAXN 2000010
using namespace std;
int t[MAXN], result[MAXN];
int num;
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;
}
}
void search(string &w, string &s) {
int i = 0, j = 0;
while (i < s.size()) {
while (j >= 0 && s[i] != w[j]) j = t[j];
++i; ++j;
if (j == w.size()) {
result[num] = i-j;
num++;
j = t[j];
}
}
}
int main() {
string s, w;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> w >> s;
preprocess(w);
num = 0;
search(w, s);
g << num << endl;
for (int i = 0; i < min(num, 1000); ++i) {
g << result[i] << " ";
}
return 0;
}