Pagini recente » Cod sursa (job #2287365) | Cod sursa (job #2909971) | Cod sursa (job #1704217) | Cod sursa (job #1375531) | Cod sursa (job #2663258)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define Nrmax 2000001
char a[Nrmax],b[Nrmax];
int pi[Nrmax],n,m,nr,poz[Nrmax];
void make_prefix()
{
int q=0;
for (int i=2;i<=m;i++)
{
while (q && a[q+1]!=a[i])
q=pi[q];
if (a[q+1]==a[i])
q++;
pi[i]=q;
}
}
int main()
{
fin>>a;
fin>>b;
for (;a[m];m++);
for (;b[n];n++);
for (int i=m;i>=0;i--)
a[i]=a[i-1];
for (int i=n;i>=0;i--)
b[i]=b[i-1];
a[0]=b[0]=' ';
//fout<<a<<'\n'<<b<<'\n';
make_prefix();
int q=0;
for (int i=1;i<=n;i++)
{
while (q && a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
q++;
if (q==m)
{
q=pi[m];
nr++;
if (nr<=1000)
poz[nr]=i-m;
}
}
fout<<nr<<'\n';
for (int i=1;i<=min(1000,nr);i++)
fout<<poz[i]<<' ';
return 0;
}