Pagini recente » pre_oni_gim2015 | Cod sursa (job #738097) | Cod sursa (job #2636852) | Cod sursa (job #2794640) | Cod sursa (job #2071735)
#include <iostream>
#include <string.h>
using namespace std;
char N[1000],H[1000];
int S[1000],vec[2000];
int n,h,f,cont;
int main()
{
cin>>N+1;
cin>>H+1;
n=strlen(N+1);
h=strlen(H+1);
/// se construieste sirul S
S[0]=-1;
S[1]=0;
for (int i=2; i<=n; i++)
{
/// se calculeaza S[i]
int p;
char c;
p=S[i-1];
c=N[i];
while (1)
{
if (p==-1)
break;
if (N[p+1]==c)
break;
p=S[p];
}
S[i]=p+1;
}
/// KMP
f=0;
for (int i=1; i<=h; i++)
{
char c;
c=H[i];
/// bucla while
int s=f;
while (1)
{
if (s==-1)
break;
if (N[s+1]==c)
break;
s=S[s];
}
f=s+1;
if (f==n)
{
vec[++cont]=i-n;
f=S[f];
}
if(cont==10)
break;
}
cout<<cont<<"\n";
for(int i=1; i<=cont; i++)
cout<<vec[i]<<" ";
return 0;
}