Pagini recente » Cod sursa (job #922345) | Cod sursa (job #1818005) | Cod sursa (job #1536655) | Cod sursa (job #1544470) | Cod sursa (job #2361584)
#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++)
{
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++)
{
while(poz!=0&&b[poz]!=a[i])
poz=v[poz-1];
if(a[i]==b[poz])
{
poz++;
if(poz==m+1)
{
ans++;
if(ans<=1000)
sol[ans]=i-m;
poz=v[m];
}
}
}
fout<<ans<<'\n';
for(i=1;i<=min(1000,ans);i++)
fout<<sol[i]<<" ";
return 0;
}