Pagini recente » Cod sursa (job #865669) | Cod sursa (job #2178632) | Cod sursa (job #2710121) | Cod sursa (job #266030) | Cod sursa (job #1522699)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector < int > get_pi(string const &W, string const &S) {
vector < int > pi(W.size());
int i, q;
pi[0] = (S[0] == W[0]);
for(i = 1; i < S.size(); i++) {
for(q = pi[i-1]; q > 1 && W[q] != S[i]; q = pi[q-1]);
if(W[q] == S[i]) q++;
pi[i] = q;
}
return pi;
}
int main() {
int i;
string S, W;
vector < int > matches;
in >> W >> S;
W += '0';
vector < int > pi = get_pi(W, S);
for(i = 0; i < S.size(); i++) {
if(pi[i] == W.size() - 1) {
if(matches.size() < 1000) {
matches.push_back(i - W.size() + 1);
}
}
}
out << matches.size() << '\n';
for(auto it : matches) out << it + 1 << ' ';
return 0;
}