Pagini recente » Cod sursa (job #1889220) | Cod sursa (job #900240) | Cod sursa (job #914886) | Cod sursa (job #1371299) | Cod sursa (job #2337821)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,i,j,l,r,ans,k,zalg[4000010];
string A,B;
int main()
{
f>>A>>B;
m=A.size();
A+='1';A+=B;
n=A.size();
for(i=2;i<=n;i++)
{
if(i>r)
{
for(j=i;j<=n;j++)
if(A[j-1]!=A[j-i])
break;
zalg[i]=j-i;
l=i;r=j-1;
}
else
{
zalg[i]=min(r-i+1,zalg[i-l+1]);
if(zalg[i]==r-i+1)
{
for(j=r+1;j<=n;j++)
if(A[j-1]!=A[j-i])
break;
zalg[i]=j-i;
l=i,r=i+zalg[i]-1;
}
}
if(zalg[i]==m)
ans++;
}
// g<<A<<'\n';
// for(i=1;i<=n;i++)
// g<<zalg[i]<<' ';g<<'\n';
g<<ans<<'\n';
int cnt=1000;
for(i=1;i<=n&&cnt;i++)
if(zalg[i]==m)
cnt--,g<<i-m-2<<' ';
return 0;
}