Pagini recente » Cod sursa (job #589671) | Cod sursa (job #1996020) | Cod sursa (job #1197420) | Cod sursa (job #1511556) | Cod sursa (job #1166555)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define len(x) int((x).size())
const int MAX_N = 2e6 + 100;
string P, T;
vector<int> pi, ans;
void kmp();
int main() {
fin >> P >> T;
P = " " + P;
T = " " + T;
kmp();
fout << len(ans) << '\n';
for (int i = 0; i < len(ans) && i < 1000; i += 1)
fout << ans[i] << ' ';
}
void kmp() {
int n = len(T) - 1, m = len(P) - 1;
pi.resize(len(P));
for (int i = 2, p = 0; i <= m; i += 1) {
while (p > 0 && P[p + 1] != P[i]) p = pi[p];
if (P[p + 1] == P[i]) p += 1;
pi[i] = p;
}
for (int i = 1, p = 0; i <= n; i += 1) {
while (p > 0 && P[p + 1] != T[i]) p = pi[p];
if (P[p + 1] == T[i]) p += 1;
if (p == m)
ans.push_back(i - m);
}
}