Pagini recente » Cod sursa (job #1357879) | Cod sursa (job #1239255) | Cod sursa (job #2255445) | oji2017simulare | Cod sursa (job #2122756)
#include <fstream>
#include <vector>
#include <cstring>
#define MAXN 2000006
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> sol;
char T[MAXN], P[MAXN];
int N, M, k, pi[MAXN];
inline void Read() {
fin >> (P + 1);
fin >> (T + 1);
N = strlen(P + 1); M = strlen(T + 1);
}
inline void Det_pi() {
int k = 0;
for (int i = 2; i <= N; i++) {
while (k > 0 && P[k + 1] != P[i]) {
k = pi[k];
}
if (P[k + 1] == P[i]) {
k++;
}
pi[i] = k;
}
}
inline void KMP() {
k = 0;
for (int i = 1; i <= M; i++) {
while (k > 0 && P[k + 1] != T[i]) {
k = pi[k];
}
if (P[k + 1] == T[i]) {
k++;
}
if (k == N) {
sol.push_back(i - N);
if (sol.size() == 1000) {
return;
}
}
}
}
inline void Afisare() {
fout << sol.size() << "\n";
int l = sol.size();
for (int i = 0; i < l; i++) {
fout << sol[i] << " ";
}
}
int main () {
Read();
Det_pi();
KMP();
Afisare();
fin.close(); fout.close(); return 0;
}