Pagini recente » Cod sursa (job #1736368) | Profil StoianRares | Cod sursa (job #147364) | Cod sursa (job #2076082) | Cod sursa (job #2373175)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prefix[2000005],sol[1005];
string a,b;
int main()
{
int i,j,n,m,ans=0;
fin>>a;
fin>>b;
n=a.size()-1;
m=b.size()-1;
prefix[0]=0;
j=0;
for(i=1;i<=n;i++)
{
while(a[i]!=a[j]&&j!=0)
j=prefix[i-1];
if(a[i]==a[j])
j++;
prefix[i]=j;
}
j=0;
for(i=0;i<=m;i++)
{
while(b[i]!=a[j]&&j!=0)
j=prefix[j-1];
if(b[i]==a[j])
{
j++;
if(j==n+1)
{
ans++;
if(ans<=1000)
sol[ans]=i-n;
j=prefix[j-1];
}
}
}
fout<<ans<<'\n';
for(i=1;i<=min(ans,1000);i++)
fout<<sol[i]<<" ";
return 0;
}