Pagini recente » Cod sursa (job #141778) | Cod sursa (job #2392967) | Cod sursa (job #2921379)
#include <bits/stdc++.h>
using namespace std;
const int NMAX=2e6+5;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//char a[NMAX],b[NMAX];
string a,b;
int m,n,i;
int z[2*NMAX];
int ans;
vector<int> poz;
int mymin(int a, int b)
{
return (a<b?a:b);
}
void solve()
{
fin>>a>>b;
m=a.length();
a="#"+a+"&"+b;
n=a.length()-1;
int l=0,r=0;
for(i=1;i<=n;i++)
{
if(i<=r)
z[i]=mymin(z[i-l+1],r-i+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=m+2;i<=n;i++)
if(z[i]==m)
{
ans++;
if(ans<=1000)
poz.push_back(i-m-2);
}
fout<<ans<<'\n';
for(auto it:poz)
fout<<it<<' ';
fout<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}