Pagini recente » Cod sursa (job #1236358) | Cod sursa (job #2324473) | Cod sursa (job #1497412) | Cod sursa (job #2116132) | Cod sursa (job #1790467)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
vector<int> AflaPrefix(const string &s)
{
vector<int> prefix(s.size(), 0);
int lung = 0;
for (unsigned i = 1; i < s.size(); ++i) {
while (lung > 0 && s[i] != s[lung])
lung = prefix[lung - 1];
if (s[i] == s[lung])
++lung;
prefix[i] = lung;
}
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;
}