Pagini recente » Borderou de evaluare (job #1205544) | Profil repp4radu | Profil Andrulian | Borderou de evaluare (job #372387) | Cod sursa (job #2722204)
#include <fstream>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int n, k, ans;
int pi[4000005];
string s1, s2, s;
void kmp() {
int p = 0;
for (int i = 2; i <= n; ++i) {
while (p > 0 && s[i] != s[p + 1])
p = pi[p];
if (s[i] == s[p + 1])
++p;
pi[i] = p;
if (pi[i] >= k)
++ans;
}
}
int main() {
cin >> s1 >> s2;
k = s1.size();
s = "#" + s1 + "#" + s2;
n = s1.size() + s2.size() + 1;
kmp();
cout << ans << '\n';
int cnt = 0;
for (int i = k + 1; i <= n && cnt < 1000; ++i) {
if (pi[i] == k) {
cout << i - k - k - 1 << ' ';
++cnt;
}
}
return 0;
}