Pagini recente » Cod sursa (job #3123011) | Cod sursa (job #1456903) | Cod sursa (job #3286194) | Cod sursa (job #288603) | Cod sursa (job #3242723)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int lps[N];
void kmp(string &s) {
int k = 0;
for(int i = 2; i < s.length(); i++) {
while(k > 0 && s[i] != s[k + 1])
k = lps[k];
if(s[i] == s[k + 1]) {
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;
int m = s.length(), n = t.length();
s = " " + s;
t = " " + t;
vector <int> ans;
kmp(s);
int k = 0;
for(int i = 1; i <= n; i++) {
while(k > 0 && t[i] != s[k + 1]) {
k = lps[k];
}
if(t[i] == s[k + 1]) {
k++;
}
if(k == m) {
ans.push_back(i-m);
if(ans.size() >= 1000) {
cout << ans.size() << "\n";
for(int x : ans) {
cout << x << " ";
}
return 0;
}
k = lps[m];
}
}
cout << ans.size() << "\n";
for(int x : ans) {
cout << x << " ";
}
return 0;
}