Pagini recente » Cod sursa (job #850019) | Cod sursa (job #159198) | Cod sursa (job #9269) | Cod sursa (job #2914473) | Cod sursa (job #3242726)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int lps[N], n, m;
void kmp(string &s) {
int k = 0;
for(int i = 1; i < n; i++) {
while(k > 0 && s[i] != s[k]) {
k = lps[k - 1];
}
if(s[i] == s[k])
k++;
lps[i] = k;
}
}
// #define HOME
int main() {
#ifndef HOME
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#endif
string s, t;
cin >> s >> t;
n = s.length();
m = t.length();
vector <int> ans;
s += "#";
kmp(s);
int k = 0;
for(int i = 0; i < m; i++) {
while(k > 0 && t[i] != s[k]) {
k = lps[k - 1];
}
if(t[i] == s[k])
k++;
if(k == n) {
ans.push_back(i - n + 1);
}
}
cout << ans.size() << "\n";
for(int i = 0; i < min((int)ans.size(), 1000); i++) {
cout << ans[i] << " ";
}
return 0;
}