Pagini recente » Cod sursa (job #2747864) | Cod sursa (job #394758) | Cod sursa (job #2879874) | Cod sursa (job #2883295) | Cod sursa (job #3151650)
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a , b;
int lps[2000001];
signed main()
{
cin >> a >> b;
int sza = a.size();
int szb = b.size();
for(int i = 0 , j = 1 ; j < sza ;)
{
if(a[i]==a[j])
{
lps[j] = lps[j-1]+1;
i++;
j++;
}
else
{
if(i) i = lps[i-1];
else j++;
}
}
vector <int> ans;
int hm = 0;
for(int i = 0 , j = 0 ; j < szb ;)
{
if(a[i]==b[j])
{
if(i<sza-1)
{
j++;
i++;
}
else
{
hm++;
if(hm<=1000)
{
ans.pb(j-sza+1);
}
i = lps[sza-1];
j++;
}
}
else
{
if(i == 0)
{
j++;
}
else i = lps[i-1];
}
}
cout << ans.size() << '\n';
for(auto &it : ans) cout << it << ' ';
return 0;
}