Pagini recente » Cod sursa (job #287328) | Cod sursa (job #3137740) | Cod sursa (job #2351083) | Cod sursa (job #247189) | Cod sursa (job #570949)
Cod sursa(job #570949)
#include <fstream>
#define InF "strmatch.in"
#define OutF "strmatch.out"
#define LgMax 2000002
using namespace std;
ifstream fin(InF);
ofstream fout(OutF);
char W[LgMax],S[LgMax];
int T[LgMax],leng,leng_W,k,V[LgMax];
void make_pref();
void kmp();
int main()
{
fin.getline(W,LgMax);
fin.get();
fin.getline(S,LgMax);
leng = strlen(S);
leng_W = strlen(W);
make_pref();
kmp();
fout<<k<<"\n";
for(int i = 0;i < k;i++)
fout<<V[i] + 1<<" ";
return 0;
}
void make_pref()
{
int pos = 2, cnd = 0;
T[0] = -1;T[1] = 0;
while(pos < leng_W)
{
if(W[pos - 1] == W[cnd])
{
cnd++;
T[pos] = cnd;
pos++;
}
else if(cnd > 0)
cnd = T[cnd];
else
T[pos] = 0, pos++;
}
}
void kmp()
{
int m = 0,i = 0;
while(i + m < leng)
{
if(W[i] == S[m + i])
{
if(i == leng_W - 1)
{
V[k++] = m;
m = m + i - T[i];
if(T[i] > -1)
i = T[i];
else
i = 0;
}
i++;
}
else
{
m = m + i - T[i];
if(T[i] > -1)
i = T[i];
else
i = 0;
}
}
}