Pagini recente » Cod sursa (job #1725120) | Cod sursa (job #1350402) | Cod sursa (job #721273) | Cod sursa (job #2837938) | Cod sursa (job #2899819)
#include <bits/stdc++.h>
using namespace std;
int nr;
vector<int> ans;
int n,m,i,j;
string a,b;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int l,r;
int z[2000007];
int mymin(int a, int b)
{
return (a < b ? a : b);
}
void solve()
{
fin>>a>>b;
n=a.length();
m=b.length();
int st = n + 2;
int lg=n;
a="%"+a+"#"+b;
n+=m+1;
for(i=2;i<=n;i++)
{
if(i<=r)
z[i]=mymin(r-i+1,z[i-l+1]);
while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+1])z[i]++;
if(i+z[i]-1>r)
{
r=i+z[i]-1;
l=i;
}
}
/*for(i=1;i<=n;i++)
cout<<a[i];
cout<<'\n';
for(i=1;i<=n;i++)
cout<<z[i]<<' ';
cout<<'\n';*/
for(i=st;i<=n;i++)
if(z[i]==lg)
{
nr++;
if(nr==1001)
{
nr=1000;
break;
}
ans.push_back(i-st);
}
fout<<nr<<'\n';
for(auto it:ans)
fout<<it<<' ';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt=1;
//cin>>tt;
for(int t=1;t<=tt;t++)
solve();
return 0;
}