Pagini recente » Cod sursa (job #1945063) | Cod sursa (job #1621607) | Borderou de evaluare (job #1762657) | Cod sursa (job #1494994) | Cod sursa (job #1196666)
#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 (j && P[j + 1] != P[i]) 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 (j && P[j + 1] != T[s]) 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 < 1000; i++) fout << S[i] - M << ' ';
return 0;
}