Pagini recente » Cod sursa (job #1488965) | Cod sursa (job #1650912) | Cod sursa (job #819430) | Cod sursa (job #565829) | Cod sursa (job #2411435)
#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) {
if(i > r) {
while(i + z[i] < a.size() && a[i+z[i]] == a[1 + z[i]]) ++ z[i];
r = i + z[i] - 1;
l = i;
} else {
z[i] = min(r - i, z[i - l + 1]);
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;
}