Pagini recente » Cod sursa (job #1476290) | Cod sursa (job #26723) | Cod sursa (job #1978976) | Cod sursa (job #2909538) | Cod sursa (job #2044062)
#include<fstream>
#include<cstring>
#include<iostream>
#define DN 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,nr,pr[DN],k,r[DN];
char a[DN],b[DN];
int main()
{
fin.getline(a,DN);
fin.getline(b,DN);
n=strlen(a);
m=strlen(b);
for(int i=n;i>=1;i--)
a[i]=a[i-1];
a[0]=' ';
for(int i=m;i>=1;i--)
b[i]=b[i-1];
b[0]=' ';
for(int i=2;i<=n;i++)
{
while(k&&a[i]!=a[k+1])
k=pr[k];
if(a[i]==a[k+1])
k++;
pr[i]=k;
}
k=0;
for(int i=1;i<=m;i++)
{
while(k&&b[i]!=a[k+1])
k=pr[k];
if(b[i]==a[k+1])
k++;
if(k==n)
{
nr++;
r[nr]=i-n;
}
}
fout<<nr<<'\n';
for(int i=1;i<=min(nr,1000);i++)
fout<<r[i]<<" ";
}