Pagini recente » Cod sursa (job #1541040) | Cod sursa (job #1541006) | Cod sursa (job #2099712) | Cod sursa (job #2141348) | Cod sursa (job #1574438)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MAX_LEN = 2000000;
char W[5 + MAX_LEN];
char S[5 + MAX_LEN];
int pi[5 + MAX_LEN];
int main() {
int i, q, n, m;
vector < int > sol;
in >> W + 1;
in >> S + 1;
n = strlen(W + 1);
m = strlen(S + 1);
for(i = 2, q = 0, pi[1] = 0; i <= m; i++) {
while(q > 0 && W[q + 1] != W[i]) q = pi[q];
if(W[q + 1] == W[i]) q++;
pi[i] = q;
}
for(i = 1, q = 0; i <= m; i++) {
while(q > 0 && W[q + 1] != S[i]) q = pi[q];
if(W[q + 1] == S[i]) q++;
if(q == n) sol.push_back(i - n);
}
out << sol.size() << '\n';
for(i = 0; i < min(sol.size(), 1000u); i++) out << sol[i] << ' ';
return 0;
}