Pagini recente » Cod sursa (job #629139) | Cod sursa (job #2094812) | Cod sursa (job #1606230) | Cod sursa (job #1904962) | Cod sursa (job #1347369)
#include <fstream>
#include <string>
#include <vector>
std::ifstream be ("strmatch.in");
std::ofstream ki ("strmatch.out");
std::string s, szo;
std::vector<int> pre, megold;
int hs, hszo;
void make_pre()
{
int last = 0;
pre.resize (hszo+1, 0);
pre[1] = 0;
for (int i=2; i<=hszo; i++) {
while (last != 0 && szo[last+1] != szo[i])
last = pre[last];
//if (last) last++;
if (szo[last+1] == szo[i]) last++;
pre[i] = last;
}
}
void kmp()
{
int last = 0;
for (int i=1; i<=hs; i++) {
while (last != 0 && s[i] != szo[last+1]) last = pre[last];
//if (last) last++;
if (s[i] == szo[last+1]) last++;
if (last == hszo) {
last = pre[last];
megold.push_back (i-hszo);
}
}
}
int main()
{
be >> szo >> s;
hs = s.length();
hszo= szo.length();
s.insert (0, " ");
szo.insert (0, " ");
make_pre();
//for (int i=1; i<=hszo; i++) ki << pre[i];
kmp();
ki << megold.size() << "\n";
int sz = megold.size(); if (sz > 1000) sz = 1000;
for (int i=0; i<sz; i++) ki << megold[i] << " ";
}