Pagini recente » Cod sursa (job #1822628) | Cod sursa (job #1820021) | Cod sursa (job #1880314) | Cod sursa (job #431632) | Cod sursa (job #1458799)
#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
#define MAX 2000001
int P[MAX],n;
char str[MAX],sub_str[MAX];
int d[1001];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
void make_prefix(int l)
{
int i=1,j=0;
while(i<l)
{
while(i<l && sub_str[i] == sub_str[j])
{
P[i]=P[i-1] + 1;
++j;
++i;
}
if(j>0 && i<l)
{
j=P[i-1];
while(j>0 && sub_str[j]!=sub_str[i])
j=P[j-1];
if(j>0)
{
P[i]=P[j];
++i,++j;
}
}
else
++i;
}
}
void KMP()
{
int l_str=strlen(str),l_substr=strlen(sub_str);
make_prefix(l_substr);
int i=0,j=0;
while(i<l_str)
{
while(j<l_substr && i<l_str && sub_str[j] == str[i] )
++i,++j;
if(j>=l_substr)
{
++n;
if(n<=1000)
{
d[n]=i-j;
}
}
if(j>0 && i<l_str)
{
j=P[j-1];
while(j>0 && sub_str[j] != str[i])
j=P[j-1];
if(j>0)
++i,++j;
}
else
++i;
}
}
int main()
{
in>>sub_str>>str;
KMP();
out<<n<<'\n';
for(int i=1;i<=1000 && i<=n;i++)
out<<d[i]<<" ";
in.close();
out.close();
return 0;
}