Pagini recente » Cod sursa (job #762502) | Cod sursa (job #1302112) | Cod sursa (job #1940418) | Cod sursa (job #2714629) | Cod sursa (job #2899015)
#include<bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string P;
in >> P;
string T;
in >> T;
int answer[1001], L = 0;
int n = T.size();
int m = P.size();
vector<int> preFunc(m, 0);
for(int i = 1; i < m; ++i) {
int k = preFunc[i - 1];
while(k && P[k] != P[i]) {
k = P[k - 1];
}
if(P[k] == P[i]) {
k++;
}
preFunc[i] = k;
}
int k = 0;
for(int i = 0; i < n; ++i) {
while(k && P[k] != T[i]) {
k = preFunc[k - 1];
}
if(P[k] == T[i]) {
k++;
}
if(k == m) {
k = preFunc[k - 1];
L++;
if(L <= 1000) {
answer[L] = i - m + 1;
}
}
}
out << min(L, 1000) << '\n';
for(int i = 1; i <= min(L, 1000); ++i) {
out << answer[i] << ' ';
}
}