Pagini recente » Cod sursa (job #1887206) | Cod sursa (job #1698042) | Cod sursa (job #3126898) | Cod sursa (job #614145) | Cod sursa (job #2969370)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
vi ans;
vi build_lps(string s){
int n = s.size();
vi lps(n);
for(int i = 1; i < n; i++){
int j = lps[i-1];
while(j > 0 && s[i] != s[j])
j = lps[j-1];
if(s[i] == s[j])
j++;
lps[i] = j;
}
return lps;
}
void solve(){
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
vi lps = build_lps(a);
int i = 0, j = 0;
while(i < m){
if(a[j] == b[i]){
j++;
i++;
}
if(j == n){
ans.pb(i - n);
j = lps[j-1];
} else if(i < m && a[j] != b[i]){
if(j == 0)
i++;
else
j = lps[j-1];
}
}
cout << ans.size() << '\n';
for(int i = 0; i < min(1000, (int)ans.size()); i++)
cout << ans[i] << ' ';
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}