Pagini recente » Cod sursa (job #143898) | Cod sursa (job #166775) | Cod sursa (job #1314937) | Cod sursa (job #2396444) | Cod sursa (job #2290768)
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#define nl '\n'
using namespace std;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
ios_base::sync_with_stdio(false);
cout.tie(0);
string N,M;
cin >> M >> N;
int n = N.size(),m = M.size();
int lps[m];
lps[0] = 0;
int i=1;
int len = 0;
while (i<m){
if(M[i] == M[len] ){
++len;
lps[i] = len;
++i;
}else{
if(len){
len = lps[len-1];
}else
lps[i] = 0,++i;
}
}
i=0;
len = 0;
int cnt = 0;
vector<int> sol;
while (i<n){
if(N[i] == M[len]){
++i;
++len;
}
if(len == m){
++cnt;
if(cnt<1000)
sol.push_back(i-m);
len = lps[len-1];
}
else if(M[len]!=N[i] && i<n){
if(len)
len = lps[len-1];
else ++i;
}
}
cout << cnt << nl;
for_each(sol.begin(),sol.end(),[](int a){cout << a << ' ';});
}