Pagini recente » Cod sursa (job #1661891) | Statistici Barbalau Bucur Matei (UNIBUC_Barbalau_Bucur_Matei) | Cowfood | Istoria paginii utilizator/nistor_dora_valentina | Cod sursa (job #3283451)
#include <bits/stdc++.h>
#define NMAX 2000000
#define ll long long
#define ull unsigned long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
int pi[NMAX + 3];
void kmp(string &s, int *pi) {
int k = 0;
for (int i = 1; i < s.size(); i++) {
while (k > 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k++;
}
pi[i] = k;
}
}
int main() {
fin >> s >> t;
kmp(s, pi);
int k = 0;
vector<int> ans;
for (int i = 0; i < t.size(); i++) {
while (k > 0 && t[i] != s[k]) {
k = pi[k - 1];
}
if (t[i] == s[k]) {
k++;
}
if (k == s.size()) {
ans.push_back(i - s.size() + 1);
k = pi[k - 1];
}
}
fout << ans.size() << '\n';
int n = ans.size();
for (int i = 0; i < min(n, 1000); i++) {
fout << ans[i] << ' ';
}
return 0;
}