Pagini recente » Monitorul de evaluare | Cod sursa (job #1040089) | Cod sursa (job #2742428) | Cod sursa (job #1602968) | Cod sursa (job #2056530)
#include <fstream>
#include <cstring>
#define MAXN 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char T[MAXN], P[MAXN];
int k, pi[MAXN], v[MAXN], nn, N, M;
inline void Read() {
fin >> (P + 1);
fin >> (T + 1);
}
inline void Det_pi() {
k = 0; pi[k] = 0;
N = strlen(P + 1);
for (int i = 2; i <= N; i++) {
while (P[i] != P[k + 1] && k > 0) {
k = pi[k];
}
if (P[i] == P[k + 1])
k++;
pi[i] = k;
}
}
inline void KMP() {
k = 0; M = strlen(T + 1);
for (int i = 1; i <= M; i++) {
while (k > 0 && T[i] != P[k + 1])
k = pi[k];
if (T[i] == P[k + 1])
k++;
if (k == N) {
if (nn < 1000) {
v[++nn] = i - N;
}
k = pi[k];
}
}
}
inline void Afisare() {
fout << nn << "\n";
for (int i = 1; i <= nn; i++) {
fout << v[i] << " ";
}
}
int main () {
Read();
Det_pi();
KMP();
Afisare();
fin.close(); fout.close(); return 0;
}