Pagini recente » Cod sursa (job #1650378) | Cod sursa (job #1204271) | Cod sursa (job #358737) | Cod sursa (job #2938228) | Cod sursa (job #788388)
Cod sursa(job #788388)
#include <cstdio>
#include <vector>
using namespace std;
#define Max 2000001
vector<int>v;
int n,nr,u[Max];
char a[Max],b[Max];
void prefix()
{
int k,i;
u[0] = k = -1;
for(int i=1;a[i]!='\n' && a[i]!='\0';n=i++)
{
while(k>-1 && a[k+1]!=a[i])k = u[k];
if(a[k+1]==a[i])k++;
u[i] = k;
}
}
void kmp()
{
int k,i;
k = -1;
for(int i=0;b[i]!='\n' && b[i]!='\0';i++)
{
while(k>-1 && a[k+1]!=b[i])k = u[k];
if(a[k+1]==b[i])k++;
if(k==n)
{
nr++;
v.push_back(i-n);
k = u[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s ",a);
scanf("%s ",b);
prefix();
kmp();
printf("%d\n",nr);
for(int i=0;i<v.size();i++)printf("%d ",v[i]);
return 0;
}