Pagini recente » Cod sursa (job #3338879) | Borderou de evaluare (job #3331151) | Profil rtlkpxubfqq | Cod sursa (job #3338880) | Cod sursa (job #3359526)
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int lps[2000010];
int main()
{
FASTIO
string a, b;
fin >> a >> b;
int n = a.length(), m = b.length();
int k = 0;
for(int i = 2; i <= n; i++){
while(k != 0 && a[k] != a[i - 1])
k = lps[k];
if(a[k] == a[i - 1]) k++;
lps[i] = k;
}
vector<int> sol;
k = 0;
for(int i = 1; i <= m; i++){
while(k != 0 && a[k] != b[i - 1])
k = lps[k];
if(a[k] == b[i - 1]) k++;
if(k == n) sol.push_back(i - n);
}
fout << sol.size() << '\n';
for(int i : sol)
fout << i << ' ';
return 0;
}