Pagini recente » Cod sursa (job #399251) | Cod sursa (job #219781)
Cod sursa(job #219781)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int t[2000000],nr_sol=0;
string w,s;
vector <int> sol;
vector <int>::iterator it;
void citire()
{
char buffer;
freopen("strmatch.in","r",stdin);
buffer=getc(stdin);
while (buffer!='\n')
{
w+=buffer;
buffer=getc(stdin);
}
buffer=getc(stdin);
while (buffer!='\n')
{
s+=buffer;
buffer=getc(stdin);
}
fclose(stdin);
}
void gen_table()
{
int poz=2, cnd=0;
t[0]=-1;
t[1]=0;
while (poz<w.length())
{
if (w[poz-1]==w[cnd])
{
t[poz]=cnd+1;
poz++;
cnd++;
}
else if (cnd>0)
cnd=t[cnd];
else
{
t[poz]=0;
poz++;
}
}
}
void gaseste()
{
int m=0,i=0;
while (m+i<s.length())
{
if (w[i] == s[m+i])
{
i++;
if (i == w.length())
{
if (nr_sol<1000)
sol.push_back(m);
nr_sol++;
m++;
i=0;
}
}
else
{
m=m+i-t[i];
if (i>0)
i=t[i];
}
}
}
int main()
{
citire();
gen_table();
gaseste();
freopen("strmatch.out","w",stdout);
printf("%d\n",nr_sol);
for (it=sol.begin(); it!=sol.end();it++)
printf("%d ",*it);
fclose(stdout);
return 0;
}