Pagini recente » Cod sursa (job #419240) | Cod sursa (job #1975666) | Cod sursa (job #3231693) | Cod sursa (job #2515901) | Cod sursa (job #2349662)
#include <bits/stdc++.h>
using namespace std;
const int NMax = 4000003;
int zf[NMax];
vector<int> ans;
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string x,y;
cin >> x;
cin >> y;
int n = x.size();
x = x + "$" + y;
int L = 0, R = 0;
for(int i = 1; i < x.size(); ++i){
if(i > R){
L = R = i;
while(R < x.size() && x[R - i] == x[R]){
R++;
}
R--;
zf[i] = R - i + 1;
}else{
if(zf[i - L] < R - i + 1){
zf[i] = zf[i - L];
}else{
L = i;
while(R < x.size() && x[R - i] == x[R]){
R++;
}
R--;
zf[i] = R - i + 1;
}
}
}
int nr = 0;
for(int i = n; i < x.size(); ++i){
if(zf[i] == n){
nr++;
if(nr <= 1000){
ans.push_back(i - n - 1);
}
}
}
cout << nr << '\n';
for(auto i : ans){
cout << i << ' ';
}
return 0;
}