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