Pagini recente » Cod sursa (job #247451) | Cod sursa (job #1845399) | Cod sursa (job #123547) | Cod sursa (job #2297599) | Cod sursa (job #3159831)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<vector>
#define NMAX 2000005
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pr[NMAX];
string A, B;
int main() {
fin >> A >> B;
A.push_back('#');
int k = 0;
for (int i = 1; i<A.size(); i++) {
while (k != 0 && A[k] != A[i]) {
k = pr[k-1];
}
if (A[k] == A[i]) {
k++;
}
pr[i] = k;
}
vector<int> ans;
k = 0;
for (int i = 0; i<B.size(); i++) {
while (k != 0 && A[k] != B[i]) {
k = pr[k-1];
}
if (A[k] == B[i]) {
k++;
}
if (k >= A.size()-1) {
ans.push_back(i - (A.size()-1) + 1);
}
}
fout << ans.size() << '\n';
for (int i = 0; i<min(1000, (int)ans.size()); i++) {
fout << ans[i] << ' ';
}
fout << '\n';
return 0;
}