Pagini recente » Cod sursa (job #2079460) | Cod sursa (job #1215948) | Cod sursa (job #1071719) | Cod sursa (job #1653314) | Cod sursa (job #1674789)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N=2000001;
char a[N+1],b[N+1];
int pref[N],n,m,c[N];
void calc()
{
int k=0,i;
for(i=2;i<=m;i++)
{
while(k>0 && a[k+1]!=a[i])
{
k=pref[k];
}
if(a[k+1]==a[i])
k++;
pref[i]=k;
}
}
int main()
{
int i,l=0;
in.getline(a+1,N);
in.getline(b+1,N);
n=strlen(b+1);
m=strlen(a+1);
calc();
int k=0;
for(i=1;i<=n;i++)
{
while(k>0 && a[k+1]!=b[i])
k=pref[k];
if(a[k+1]==b[i])
k++;
if(k==m)
{
l++;
c[l]=i-m+1;
}
}
out<<l<<'\n';
for(i=1;i<=l;i++)
{
out<<c[i]-1<<" ";
}
return 0;
}