Pagini recente » Cod sursa (job #2326263) | Cod sursa (job #1344095) | Cod sursa (job #2897828) | Cod sursa (job #1346864) | Cod sursa (job #2315412)
#include <fstream>
#include <cstring>
#include <vector>
#define MAXN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char x[MAXN], y[MAXN];
vector <int> s;
int pi[MAXN];
inline void Read(int &N, int &M, char x[], char y[]) {
fin >> (x + 1);
N = strlen(x + 1);
fin >> (y + 1);
M = strlen(y + 1);
}
inline void Det_pi(int N, char x[], int pi[]) {
int k = 0; pi[1] = 0;
for (int i = 2; i <= N; i++) {
while (k > 0 && x[i] != x[k + 1])
k = pi[k];
if (x[i] == x[k + 1])
k++;
pi[i] = k;
}
}
inline void KMP(int N, int M, char x[], char y[], int &sol, int pi[]) {
int k = 0; sol = 0;
for (int i = 1; i <= M; i++) {
while (k > 0 && y[i] != x[k + 1])
k = pi[k];
if (y[i] == x[k + 1])
k++;
if (k == N) {
sol++;
if (sol <= 1000)
s.push_back(i - N);
k = pi[k];
}
}
}
inline void Write(int sol) {
fout << sol << "\n";
for (auto i : s)
fout << i << " ";
}
int main () {
int N, M, sol;
Read(N, M, x, y);
Det_pi(N, x, pi);
KMP(N, M, x, y, sol, pi);
Write(sol);
fin.close(); fout.close(); return 0;
}