Pagini recente » Cod sursa (job #285139) | Cod sursa (job #2686995) | Cod sursa (job #3002789) | Cod sursa (job #1332138) | Cod sursa (job #3216231)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define eb emplace_back
using ll = long long;
using ld = long double;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str,pat;
vi kmp() {
int n = str.size();
vi p(n);
for (int i = 1; i < n; ++i) {
int j = p[i - 1];
while(j>0 && str[i] != str[j])
j = p[j-1];
if (str[i]==str[j])++j;
p[i]=j;
}
return p;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin >> pat >> str;
str = pat + "$" + str;
vector<int> pref = kmp();
vector<int> ans;
int cnt = 0;
for (int i = pat.size() + 1; i < str.size(); ++i)
if (pref[i] == pat.size()) {
++cnt;
if ((int)ans.size() < 1000)
ans.emplace_back(i - pat.size() - 1);
}
fout << cnt << '\n';
for (auto i : ans)
fout << i-pat.size()+1 << ' ';
}