Pagini recente » Cod sursa (job #225928) | Cod sursa (job #1592776) | Cod sursa (job #1112534) | Cod sursa (job #1250966) | Cod sursa (job #2411433)
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#else
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string a, b;
cin >> a >> b;
int n = a.size();
vector< int > sol;
int cnt =0 ;
a = ' ' + a + '$' + b;
vector< int > z(a.size(), 0);
int l = 1, r = 1;
for(int i = 2; i < a.size(); ++i) {
z[i] = (i > r) ? 0 : min(z[i-l+1], r - i);
while(i + z[i] < a.size() && a[i+z[i]] == a[1+z[i]]) ++ z[i];
if(i + z[i] - 1 >= r) {
r = i + z[i] - 1;
l = i;
}
if(z[i] == n) {
cnt ++ ;
if(cnt <= 1000) sol.emplace_back(i - n - 2);
}
}
cout << cnt << '\n';
for(auto &x : sol) cout << x << ' ';
return 0;
}