Cod sursa(job #921494)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
static const int MAXN = 2000009;
int prefix[MAXN];
char T[MAXN], P[MAXN];
vector<int> ans;
int total = 0;
void comp_prefix() {
int k = prefix[0] = 0;
for(int i = 1; P[i]; i++) {
while(k > 0 && P[i] != P[k - 1]) k = prefix[k - 1];
if(P[k] == P[i]) k++;
prefix[i] = k;
}
}
void potriveste() {
for(int i = 0, k = 0; T[i]; i++) {
while(k > 0 && P[k] != T[i]) k = prefix[k - 1];
if(P[k] == T[i]) k++;
if(!P[k]) {
total++;
if(total < 1000) ans.push_back(i - k + 1);
}
}
}
int main() {
ifstream f("strmatch.in");
f >> P >> T;
f.close();
comp_prefix();
potriveste();
ofstream g("strmatch.out");
g << total << endl;
for(int i = 0; i < ans.size(); i++) {
g << ans[i] << ' ';
}
g.close();
return 0;
}