Pagini recente » Cod sursa (job #1512943) | Cod sursa (job #1744765) | Cod sursa (job #3244246) | Cod sursa (job #2165046) | Cod sursa (job #221143)
Cod sursa(job #221143)
#include <iostream>
#include <string>
#define nmax 2000010
using namespace std;
string w,s;
int lim,pos,i,j,t[nmax],sol[1005];
void citire()
{
char c;
freopen("strmatch.in","r",stdin);
c=getc(stdin);
while (c!='\n')
{
w+=c;
c=getc(stdin);
}
c=getc(stdin);
while (c!='\n')
{
s+=c;
c=getc(stdin);
}
fclose(stdin);
}
void create_table()
{
int pos=2;
int cnd=0;
t[0]=-1;
t[1]=0;
while (pos<=s.length())
{
if (w[pos-1]==w[cnd])
{
t[pos]=cnd+1;
pos++;
cnd++;
}
else
if (cnd>0) cnd=t[cnd];
else
{
t[pos]=0;
pos++;
}
}
}
void search_it()
{
int j=0,m=0,i=0;
while (m+i<=s.length())
{
if (w[i] == s[m+i])
{
i++;
if (i==w.length())
{
if (j<1000)
{
sol[j]=m;
j++;
}
m++;
i=0;
}
}
else
{
m=m+i-t[i];
if (i>0) i=t[i];
}
}
lim=j;
}
int main()
{
citire();
create_table();
freopen("strmatch.out","w",stdout);
search_it();
cout<<lim<<endl;
for (i=0;i<lim;i++)
cout<<sol[i]<<' ';
return 0;
}