Pagini recente » Cod sursa (job #2041927) | Cod sursa (job #2658009) | Cod sursa (job #1064092) | Cod sursa (job #2981550) | Cod sursa (job #1515555)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
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);
lgs=strlen(s);
for(int i=lgsubs;i>=0;i--)
subs[i]=subs[i-1];
for(int i=lgs;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;
queue <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-1)
{
nr++;
if(nr<=1000)
sol.push(i-a+1);
a=P[a];
}
}
}
int main()
{
freopen("strmatch.out","w",stdout);
citire();
prefix();
cauta();
printf("%d\n",nr);
while(!sol.empty())
{
printf("%d ",sol.front());
sol.pop();
}
return 0;
}