Pagini recente » Cod sursa (job #2377830) | Cod sursa (job #382829) | Cod sursa (job #1113843) | Cod sursa (job #1804028) | Cod sursa (job #1196664)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define DMAX 2000001
string P, T;
vector<int> S;
int Prefix[DMAX];
int main(){
int i, j, M, N, lg, s; char x;
fin >> P; fin.get(x); fin >> T;
P = ' ' + P; T = ' ' + T;
M = P.size();
for (Prefix[1] = 0, j = 0, i = 2; i < M; i++){
while (P[j + 1] != P[i] && j) j = Prefix[j];
if (P[j + 1] == P[i]) j++;
Prefix[i] = j;
}
N = T.size(); M--;
for (j = 0, s = 1; s < N; s++){
while (P[j + 1] != T[s] && j) j = Prefix[j];
if (P[j + 1] == T[s]) j++;
if (j == M) S.push_back(s), j = Prefix[j];
}
lg = S.size();
fout << lg << '\n';
for (i = 0; i < lg; i++) fout << S[i] - M << ' ';
return 0;
}