Pagini recente » Cod sursa (job #1469571) | Cod sursa (job #418561) | Cod sursa (job #566701) | Cod sursa (job #2509320) | Cod sursa (job #3242901)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
string s;
int pi[N]; // cel mai lung sufix propriu egal cu un prefix
void kmp(string &s, int *pi) {
int k = 0;
for(int i = 1; i < s.length(); i++) {
while(k > 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if(s[i] == s[k]) {
k++;
}
pi[i] = k;
}
}
int z[2 * N];
void Z(string &s, int *z) {
int l = 0, r = 0; // [l, r)
int n = s.length();
for(int i = 1; i < n; i++) {
z[i] = 0;
if(i < r) {
z[i] = min(z[i - l], r - i);
}
while(i + z[i] < n && s[i + z[i]] == s[z[i]]) {
z[i]++;
}
if(i + z[i] > r) {
l = i;
r = i + z[i];
}
}
}
// #define HOME
int main() {
#ifndef HOME
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#endif
string s, t;
cin >> s >> t;
int n = s.length();
s += "#" + t;
Z(s, z);
vector <int> ans;
for(int i = n + 1; i < s.length(); i++) {
if(z[i] == 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;
}