Pagini recente » Cod sursa (job #1373817) | Cod sursa (job #1709276) | Cod sursa (job #238018) | Cod sursa (job #456805) | Cod sursa (job #1798381)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,urm[2000001],m,i,k,v[2001],q,nr;
char a[2000001],b[2000001];
int main()
{
f.getline(a,2000002);
n=strlen(a);
urm[1]=0;
k=0;
for (i=2;i<=n;i++)
{
while (k>0&&a[k]!=a[i-1])
{
k=urm[k];
}
if (a[k]==a[i-1])
{
k++;
}
urm[i]=k;
}
f.getline(b,2000001);
q=0;
m=strlen(b);
for (i=0;i<m;i++)
{
while (q>0&&a[q]!=b[i])
{
q=urm[q];
}
if (a[q]==b[i])
{
q++;
}
if (q==n)
{
nr++;
if (nr<=1000)
{
v[nr]=i-n+1;
}
}
}
g<<nr<<'\n';
if (nr<=1000)
{
for (i=1;i<=nr;i++)
{
g<<v[i]<<" ";
}
}
else
{
for (i=1;i<=1000;i++)
{
g<<v[i]<<" ";
}
}
return 0;
}