Pagini recente » Cod sursa (job #445476) | Cod sursa (job #1971893) | Cod sursa (job #106878) | Cod sursa (job #2403601) | Cod sursa (job #3241819)
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
using namespace std;
const int maxn=1e5+5;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix_funciton(string s) {
int n = (int)s.length();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
return pi;
}
void solve() {
string t;
string s;
fin >> s;
fin >> t;
string temp = s + '#' + t;
int sz = s.size() + t.size() + 1;
auto pi = prefix_funciton(temp);
int counter = 0;
vector<int> ans;
for (int i = 0; i < sz; i++) {
if (ans.size() > 1000) break;
if (pi[i] == s.size()) {
//cout << i - 2 * s.size() << " ";
counter++;
ans.pb(i - 2 * s.size());
}
}
fout << counter << endl;
for (auto v : ans) {
fout << v << " ";
}
return;
}
int main() {
int t = 1;
//cin >> t;
while(t--) {
solve();
}
return 0;
}