Pagini recente » Cod sursa (job #3252247) | Cod sursa (job #2596535) | Cod sursa (job #1557491) | Cod sursa (job #1067314) | Cod sursa (job #1515563)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
char s[10000];
char subs[10000];
int P[1000];
int lgsubs,lgs;
void citire()
{
freopen("strmatch.in","r",stdin);
fgets(s,sizeof(s),stdin);
fgets(subs,sizeof(subs),stdin);
lgsubs=strlen(subs)-1;
lgs=strlen(s)-1;
for(int i=lgsubs+1;i>=0;i--)
subs[i]=subs[i-1];
for(int i=lgs+1;i>=0;i--)
s[i]=s[i-1];
subs[0]=' ';
s[0]=' ';
}
void prefix()
{
int a=0;
for(int i=2;i<=lgsubs;i++)
{
while(a && subs[a+1]!=subs[i])
a=P[a];
if(subs[i]==subs[a+1])
a++;
P[i]=a;
}
}
int nr;
vector <int> sol;
void cauta()
{
int a=0;
for(int i=1;i<=lgs;i++)
{
while(a && s[i]!=subs[a+1])
a=P[a];
if(s[i]==subs[a+1])
a++;
if(a==lgsubs)
{
a=P[a];
nr++;
if(nr<=1000)
sol.push_back(i-lgsubs);
}
}
}
int main()
{
freopen("strmatch.out","w",stdout);
citire();
prefix();
cauta();
printf("%d\n",nr);
for(int i=0;i<min(nr,1000);i++)
printf("%d ",sol[i]);
return 0;
}