Pagini recente » Cod sursa (job #2497200) | Cod sursa (job #1395533) | Cod sursa (job #1697201) | Cod sursa (job #2289475) | Cod sursa (job #2899185)
#include<bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main() {
string P;
in >> P;
string T;
in >> T;
vector<int> sol;
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 = preFunc[k - 1];
}
if(k != 0) {
preFunc[i] = k + 1;
} else {
preFunc[i] = P[0] == P[k] ? 1 : 0;
}
}
int i = 0, k = 0, answer = 0;
while(i + m - 1 < n) {
if(k != m && P[k] == T[i + k]) {
k++;
} else if(k > 0) {
if(k == m) {
answer++;
if(sol.size() < 1000) {
sol.push_back(i);
}
}
i += k - preFunc[k - 1];
k = preFunc[k - 1];
} else {
i++;
}
}
out << answer << '\n';
for(auto it : sol) {
out << it << ' ';
}
}