Pagini recente » Cod sursa (job #377424) | Cod sursa (job #40143) | Cod sursa (job #1702937) | Cod sursa (job #517718) | Cod sursa (job #2152192)
#include <fstream>
#include <vector>
#include <cstring>
#define MAXN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N, M, solutie, pi[MAXN];
char T[MAXN], P[MAXN];
vector <int> sol;
inline void Read() {
fin >> (P + 1); N = strlen(P + 1);
fin >> (T + 1); M = strlen(T + 1);
}
inline void Det_pi() {
int k = 0;
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() {
int k = 0;
for (int i = 1; i <= M; i++) {
while (T[i] != P[k + 1] && k > 0) {
k = pi[k];
}
if (T[i] == P[k + 1])
k++;
if (k == N) {
solutie++;
if (solutie <= 1000) {
sol.push_back(i - k);
}
k = pi[k];
}
}
}
inline void Afisare() {
fout << solutie << "\n";
for (auto x : sol) {
fout << x << " ";
}
}
int main () {
Read();
Det_pi();
KMP();
Afisare();
fin.close(); fout.close(); return 0;
}