Pagini recente » Cod sursa (job #105470) | Cod sursa (job #2346869) | Cod sursa (job #703042) | Cod sursa (job #1703373) | Cod sursa (job #2290038)
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nl '\n'
using namespace std;
int v[2000002];
char a[2000002];
char b[2000002];
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin >> a >> b;
auto n = strlen(a),m=strlen(b);
v[0] = -1;
auto j = 0;
for(auto i=0;i<n;){
j = 0;
++i;
while (a[i] == a[j]) {
v[i] = j;
++i;
++j;
}
v[i] = -1;
}
j = 0;
vector<int> sol;
for(auto i =0;i<m;++i){
while (b[i]!=a[j+1]){
if(!j) break;
j = v[j];
}
if(b[i] == a[j+1]) ++j;
if(j == n-1) {
sol.push_back(i-n+1);
}
}
cout << sol.size() << nl;
for_each(sol.begin(),sol.end(),[](auto n){cout << n << ' ';});
/*
for(auto i=0;i<n;++i){
cout << v[i] << ' ';
}
*/
return 0;
}