Pagini recente » Cod sursa (job #2959332) | Cod sursa (job #1927235) | Cod sursa (job #2924849) | Cod sursa (job #310251) | Cod sursa (job #2162833)
#include <bits/stdc++.h>
using namespace std;
const string IN("file.in");
const string OUT("file.out");
const int N = int(2e5 + 2);
int n, m, pi[N];
char a[N], b[N], aux[N];
vector<int>Kmp() {
int size_ = n + m + 1;
for(int i = 1; i <= n; ++i)aux[i] = a[i];
aux[n + 1] = '#';
for(int i = 1; i <= m; ++i)
aux[n + 1 + i] = b[i];
vector<int>matches;
for(int i = 2; i <= n + m + 1; ++i) {
int j = pi[i - 1];
while(j > 0 && aux[j + 1] != aux[i])
j = pi[j];
if(aux[j + 1] == aux[i])
++j;
pi[i] = j;
if(i > n + 1 && pi[i] == n) {
matches.push_back(i - 2 * n - 1);
}
}
return matches;
}
int main() {
ifstream cin(IN);
ofstream cout(OUT);
cin >> (a + 1) >> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
auto matches = Kmp();
cout << matches.size() << '\n';
matches.resize(min(1000, (int)matches.size()));
for(int i : matches)
cout << i << ' ';
}