Pagini recente » Cod sursa (job #1762212) | Cod sursa (job #1556968) | Cod sursa (job #1797589) | Autentificare | Cod sursa (job #2071740)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[1000],H[1000];
int S[1000],vec[2000];
int n,h,f,cont;
int main()
{
fin>>N+1;
fin>>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)
{
cont++;
if(cont<=1000)
vec[cont]=i-n;
f=S[f];
}
}
fout<<cont<<"\n";
if(cont>1000)
cont=1000;
for(int i=1; i<=cont; i++)
fout<<vec[i]<<" ";
fin.close();
fout.close();
return 0;
}