Pagini recente » Istoria paginii runda/bv_10/clasament | Istoria paginii runda/rar19/clasament | Cod sursa (job #2572588) | Cod sursa (job #1457581) | Cod sursa (job #1790455)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<int> AflaPrefix(const string &s)
{
vector<int> prefix;
prefix.push_back(0);
for (unsigned i = 1; i < s.size(); ++i) {
prefix.push_back(prefix[i - 1]);
while (prefix[i] != 0 && s[i] != s[prefix[i - 1]])
prefix[i] = prefix[prefix[i - 1]];
if (s[i] == s[prefix[i]])
++prefix[i];
}
return prefix;
}
vector<int> AflaPotriviri(const string &sir, const string &model)
{
auto prefix = AflaPrefix(model);
vector<int> pozitii;
unsigned lung = 0;
for (unsigned i = 0; i < sir.size(); ++i) {
while (lung > 0 && sir[i] != model[lung])
lung = prefix[lung - 1];
if (sir[i] == model[lung])
++lung;
if (lung == model.size())
pozitii.push_back(i - lung + 1);
}
return pozitii;
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string cautat;
getline(fin, cautat);
string sir;
getline(fin, sir);
auto pozitii = AflaPotriviri(sir, cautat);
fout << pozitii.size() << "\n";
for (int poz : pozitii)
fout << poz << " ";
return 0;
}