Pagini recente » Cod sursa (job #943337) | Cod sursa (job #1005758) | Cod sursa (job #1628796) | Cod sursa (job #2483438) | Cod sursa (job #2435477)
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fi("strmatch.in");
long int lps[2000010];
char a[2000010];
char b[2000010];
long int n,m;
long int nr;
long int vec[2000010];
void cit()
{
fi>>a>>b;
}
void lpss()
{
long int i,j;
i=0;
j=1;
n=strlen(a);
m=strlen(b);
lps[0]=0;
while(j<n)
if(a[i]==a[j])
{
i++;
lps[j]=i;
j++;
}
else
if(i!=0)
i=lps[i-1];
else
{
lps[j]=0;
j++;
}
}
void KMP()
{
long int i,j;
i=j=0;
lpss();
while(i<m)
{if(a[j]==b[i])
{i++;
j++;}
if(j==n)
{
vec[++nr]=i-j;
j=lps[j-1];
}
else
if(i<m&&a[j]!=b[i])
if(j!=0)
j=lps[j-1];
else
i++;}
}
int main()
{
fi>>a>>b;
lpss();
KMP();
cout<<nr<<'\n';
for(long int i=1;i<=nr;i++)
cout<<vec[i]<<" ";
return 0;
}